Complexity of Semialgebraic Proofs with Restricted Degree of Falsity

Edward A. Hirsch, Arist Kojevnikov, Alexander S. Kulikov, Sergey I. Nikolenko

Abstract


The degree of falsity of an inequality in Boolean variables shows how many variables are enough to substitute in order to satisfy the inequality. Goerdt introduced a weakened version of the Cutting Plane (CP) proof system with a restriction on the degree of falsity of intermediate inequalities [6]. He proved an exponential lower bound for CP proofs with degree of falsity bounded by n/(log^2n+1) , where n is the number of variables

In this paper we strengthen this result by establishing a direct connection between CP and Resolution proofs. This result implies an exponential lower bound on the proof length of Tseitin-Urquhart tautologies when the degree of falsity is bounded by cn for some constant c. We also generalize the notion of degree of falsity for extensions of Lov ́sz-Schrijver calculi a (LS), namely for LSk +CPk proof systems introduced by Grigoriev et al. [8]. We show that any LSk +CPk proof with bounded degree of falsity can be transformed into a Res(k) proof.  We also prove lower and upper bounds on the proof length of tautologies in LSk +CPk with bounded degree of falsity.


Keywords


propositional proof system, lower bound, algebraic proof system, Cutting Planes, Lovasz-Schrijver proof system

Full Text:

PDF

Refbacks

  • There are currently no refbacks.