Finding a tree structure in a resolution proof is NP-complete
The resolution tree problem consists of deciding whether a given sequence-like resolution refutation admits a tree structure. This paper shows the NP-completeness of both the resolution tree problem and a natural generalization of the resolution tree problem that does not involve resolution. (C) 2009 Elsevier B.V. All rights reserved.
resolution np-completeness tree-like resolution