### Complexity of Semialgebraic Proofs with Restricted Degree of Falsity

#### 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

#### Full Text:

PDF### Refbacks

- There are currently no refbacks.