Pool resolution is NP-hard to recognize
From MaRDI portal
Publication:1042441
DOI10.1007/s00153-009-0152-4zbMath1185.03084MaRDI QIDQ1042441
Publication date: 14 December 2009
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00153-009-0152-4
03B35: Mechanization of proofs and logical operations
03F07: Structure of proofs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03F20: Complexity of proofs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The NP-hardness of finding a directed acyclic graph for regular resolution
- Finding a tree structure in a resolution proof is NP-complete
- Minimum propositional proof length is NP-hard to linearly approximate
- Resolution Is Not Automatizable Unless W[P Is Tractable]
- Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning
- Pool Resolution and Its Relation to Regular Resolution and DPLL with Clause Learning