Automating Resolution is NP-Hard
- 1 September 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 67 (5), 1-17
- https://doi.org/10.1145/3409472
Abstract
We show that the problem of finding a Resolution refutation that is at most polynomially longer than a shortest one is NP-hard. In the parlance of proof complexity, Resolution is not automatable unless P = NP. Indeed, we show that it is NP-hard to distinguish between formulas that have Resolution refutations of polynomial length and those that do not have subexponential length refutations. This also implies that Resolution is not automatable in subexponential time or quasi-polynomial time unless NP is included in SUBEXP or QP, respectively.Keywords
Funding Information
- European Research Council (ERC-2014-CoG 648276)
- MICCIN (TIN2016-76573-C2-1P)
This publication has 27 references indexed in Scilit:
- Mean-payoff games and propositional proofsInformation and Computation, 2011
- Resolution Is Not Automatizable Unless W[P] Is TractableSIAM Journal on Computing, 2008
- On the automatizability of resolution and related propositional proof systemsInformation and Computation, 2004
- Minimum propositional proof length is NP-hard to linearly approximateThe Journal of Symbolic Logic, 2001
- Short proofs are narrow—resolution made simpleJournal of the ACM, 2001
- On the weak pigeonhole principleFundamenta Mathematicae, 2001
- Some Consequences of Cryptographical Conjectures forS12and EFInformation and Computation, 1998
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmeticThe Journal of Symbolic Logic, 1997
- Complexity of finding short resolution proofsLecture Notes in Computer Science, 1997
- The relative efficiency of propositional proof systemsThe Journal of Symbolic Logic, 1979