Complexity of Semialgebraic Proofs with Restricted Degree of Falsity 1 2

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 $\frac{\mathit{n}}{{log}^2\mathit{n}+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 $\mathit{c}\mathit{n}$ for some constant c. We also generalize the notion of degree of falsity for extensions of Lovász-Schrijver calculi (LS), namely for ${\mathrm{LS}}^{\mathit{k}}+{\mathrm{CP}}^{\mathit{k}}$ proof systems introduced by Grigoriev et al. [8]. We show that any ${\mathrm{LS}}^{\mathit{k}}+{\mathrm{CP}}^{\mathit{k}}$ proof with bounded degree of falsity can be transformed into a $\mathrm{Res}\mathrm{(}\mathit{k}\mathrm{)}$ proof. We also prove lower and upper bounds on the proof length of tautologies in ${\mathrm{LS}}^{\mathit{k}}+{\mathrm{CP}}^{\mathit{k}}$ with bounded degree of falsity.