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-049 | 17th April 2020 01:02

Automating Cutting Planes is NP-Hard

RSS-Feed




TR20-049
Authors: Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi
Publication: 17th April 2020 01:12
Downloads: 153
Keywords: 


Abstract:

We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula $F$,

(1) it is NP-hard to find a CP refutation of $F$ in time polynomial in the length of the shortest such refutation; and

(2) unless Gap-Hitting-Set admits a nontrivial algorithm, one cannot find a tree-like CP refutation of $F$ in time polynomial in the length of the shortest such refutation.

The first result extends the recent breakthrough of Atserias and Muller (FOCS 2019) that established an analogous result for Resolution. Our proofs rely on two new lifting theorems: (1) Dag-like lifting for gadgets with many output bits. (2) Tree-like lifting that simulates an $r$-round protocol with gadgets of query complexity $O(\log r)$ independent of input length.



ISSN 1433-8092 | Imprint