Skip to main content
eScholarship
Open Access Publications from the University of California

Pool resolution is NP-hard to recognize

  • Author(s): Buss, Samuel R.
  • et al.
Abstract

A pool resolution proof is a dag-like resolution proof which admits a depth-first traversal tree in which no variable is used as a resolution variable twice on any branch. The problem of determining whether a given dag-like resolution proof is a valid pool resolution proof is shown to be NP-complete.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View