On Sparser Random 3SAT Refutation Algorithms and Feasible InterpolationReport as inadecuate



 On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation


On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation - Download this document for free, or read online. Document in PDF available to download.

Download or read this book online for free in PDF: On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation
We formalize a combinatorial principle, called the 3XOR principle, due to Feige, Kim and Ofek 2006, as a family of unsatisfiable propositional formulas for which refutations of small size in any propositional proof system that possesses the feasible interpolation property imply an efficient deterministic refutation algorithm for random 3SAT with n variables and \Omegan^{1.4} clauses. Such small size refutations would improve the current best with respect to the clause density efficient refutation algorithm, which works only for \Omegan^{1.5} many clauses Feige and Ofek 2007. We then study the proof complexity of the above formulas in weak extensions of cutting planes and resolution. Specifically, we show that there are polynomial-size refutations of the 3XOR principle in resolution operating with disjunctions of quadratic equations with small integer coefficients, denoted Rquad. We show that Rquad is weakly automatizable iff Rlin is weakly automatizable, where Rlin is similar to Rquad but with linear instead of quadratic equations, introduced in Raz and Tzameret 2008. This reduces the question of the existence of efficient deterministic refutation algorithms for random 3SAT with n variables and \Omegan^{1.4} clauses to the question of feasible interpolation of Rquad and to the weak automatizability of Rlin.



Author: Iddo Tzameret

Source: https://archive.org/







Related documents