Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR16-175 | 13th November 2018 18:45

Random resolution refutations

RSS-Feed




Revision #2
Authors: Pavel Pudlak, Neil Thapen
Accepted on: 13th November 2018 18:45
Downloads: 9
Keywords: 


Abstract:

We study the \emph{random resolution} refutation system defined in~[Buss et al. 2014]. This attempts to capture the notion of a resolution refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the other hand, if ${\bf P}\neq{\bf NP}$, then random resolution cannot be polynomially simulated by any proof system in which correctness of proofs is checkable in polynomial time.

We prove several upper and lower bounds on the width and size of random resolution refutations of explicit and random unsatisfiable CNF formulas. Our main result is a separation between polylogarithmic width random resolution and quasipolynomial size resolution, which solves the problem stated in~[Buss et al. 2014]. We also prove exponential size lower bounds on random resolution refutations of the pigeonhole principle CNFs, and of a family of CNFs which have polynomial size refutations in constant depth Frege.



Changes to previous version:

We changed the statement of the Fixing Lemma to a more natural form. The proofs remain essentially the same.


Revision #1 to TR16-175 | 22nd December 2016 14:53

Random resolution refutations





Revision #1
Authors: Pavel Pudlak, Neil Thapen
Accepted on: 22nd December 2016 14:53
Downloads: 318
Keywords: 


Abstract:

We study the \emph{random resolution} refutation system defined in~[Buss et al. 2014]. This attempts to capture the notion of a resolution refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the other hand, if ${\bf P}\neq{\bf NP}$, then random resolution cannot be polynomially simulated by any proof system in which correctness of proofs is checkable in polynomial time.

We prove several upper and lower bounds on the width and size of random resolution refutations of explicit and random unsatisfiable CNF formulas. Our main result is a separation between polylogarithmic width random resolution and quasipolynomial size resolution, which solves the problem stated in~[Buss et al. 2014]. We also prove exponential size lower bounds on random resolution refutations of the pigeonhole principle CNFs, and of a family of CNFs which have polynomial size refutations in constant depth Frege.



Changes to previous version:

In this version we have corerected several misprints and a minor error discovered by Michal Garlik. In particular, in Lemma 4.1 we had to change the parameter $p$.


Paper:

TR16-175 | 8th November 2016 13:02

Random resolution refutations





TR16-175
Authors: Pavel Pudlak, Neil Thapen
Publication: 8th November 2016 13:04
Downloads: 441
Keywords: 


Abstract:

We study the \emph{random resolution} refutation system defined in~[Buss et al. 2014]. This attempts to capture the notion of a resolution refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the other hand, if ${\bf P}\neq{\bf NP}$, then random resolution cannot be polynomially simulated by any proof system in which correctness of proofs is checkable in polynomial time.

We prove several upper and lower bounds on the width and size of random resolution refutations of explicit and random unsatisfiable CNF formulas. Our main result is a separation between polylogarithmic width random resolution and quasipolynomial size resolution, which solves the problem stated in~[Buss et al. 2014]. We also prove exponential size lower bounds on random resolution refutations of the pigeonhole principle CNFs, and of a family of CNFs which have polynomial size refutations in constant depth Frege.



ISSN 1433-8092 | Imprint