Several notes on the power of Gomory-Chvátal cuts (Q2498920): Difference between revisions

The paper studies several algebraic proof systems based on linear programming (LP), namely variants of the lift-and-project (L\&P) system of \textit{E.~Balas}, \textit{S.~Ceria} and \textit{G.~Cor\-nué\-jols} [Math. Program., Ser.~A 58, No.~3, 295--324 (1993; Zbl 0796.90041)], the cutting plane (CP) system [\textit{V.~Chvátal}, Discrete Math. 4, 305--337 (1973; Zbl 0253.05131)], and their resolution extensions in the spirit of \textit{J. Krajíček} [J. Symb. Log.~63, No.~4, 1582--1596 (1998; Zbl 0930.03081)]. The authors prove that CP polynomially simulates L\&P proofs whose coefficients are restricted to integer numbers written in unary. Moreover, the resolution extension R(LP) polynomially simulates R(CP) proofs with the same restriction, and R(L\&P) and R(LP) are polynomially equivalent without any restriction on the coefficients. The last part of the paper presents polynomial-size R(LP) proofs of Tseitin tautologies for regular graphs of constant degree, based on \textit{D.~Grigoriev}, \textit{E.~A.~Hirsch} and \textit{D.~V.~Pasechnik} [Mosc. Math. J.~2, No.~4, 647--679 (2002; Zbl 1027.03044)].