Back to Search
Start Over
Automating Resolution is NP-hard
- Publication Year :
- 2019
-
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 automatizable 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 automatizable in subexponential time or quasi-polynomial time unless~NP is included in SUBEXP or QP, respectively.<br />Peer Reviewed<br />Postprint (author's final draft)
Details
- Database :
- OAIster
- Notes :
- 12 p., application/pdf, English
- Publication Type :
- Electronic Resource
- Accession number :
- edsoai.on1141701005
- Document Type :
- Electronic Resource