Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-012 | 21st January 2003 00:00

Several notes on the power of Gomory-Chvatal cuts

RSS-Feed




TR03-012
Authors: Edward Hirsch, Arist Kojevnikov
Publication: 7th March 2003 14:12
Downloads: 3474
Keywords: 


Abstract:

We prove that the Cutting Plane proof system based on
Gomory-Chvatal cuts polynomially simulates the
lift-and-project system with integer coefficients
written in unary. The restriction on coefficients can be
omitted when using Krajicek's cut-free Gentzen-style extension
of both systems. We also prove that Tseitin tautologies
have short proofs in this extension (of any of these systems
and with any coefficients).



ISSN 1433-8092 | Imprint