All reports by Author Sergey I. Nikolenko:

__
TR05-006
| 28th December 2004
__

Edward Hirsch, Sergey I. Nikolenko#### Simulating Cutting Plane proofs with restricted degree of falsity by Resolution

Comments: 1

Edward Hirsch, Sergey I. Nikolenko

Goerdt (1991) considered a weakened version of the Cutting Plane proof system with a restriction on the degree of falsity of intermediate inequalities. (The degree of falsity of an inequality written in the form $\sum a_ix_i+\sum b_i(1-x_i)\ge c,\ a_i,b_i\ge0$ is its constant term $c$.) He proved a superpolynomial lower bound ... more >>>