The NP-hardness of finding a directed acyclic graph for regular resolution
Let R be a resolution refutation, given as a sequence of clauses without explicit description of the underlying dag. Then, it is NP-complete to decide whether R is a regular resolution refutation. (C) 2008 Elsevier B.V. All rights reserved.
directed acyclic graph regular resolution resolution np-completeness