You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Complexity of Semialgebraic Proofs with Restricted Degree of Falsity12

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 nlog2n+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 (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.