Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-105 | 14th July 2020 02:59

Automating Regular or Ordered Resolution is NP-Hard

RSS-Feed




TR20-105
Authors: Zoë Bell
Publication: 14th July 2020 16:43
Downloads: 94
Keywords: 


Abstract:

We show that is hard to find regular or even ordered (also known as Davis-Putnam) Resolution proofs, extending the breakthrough result for general Resolution from Atserias and Müller to these restricted forms. Namely, regular and ordered Resolution are automatable if and only if P = NP. Specifically, for a CNF formula $F$ the problem of distinguishing between the existence of a polynomial-size ordered Resolution refutation of $F$ and an at least exponential-size general Resolution proof being required to refute $F$ is NP-complete.



ISSN 1433-8092 | Imprint