Several notes on the power of Gomory–Chvátal cuts

&
Annals of Pure and Applied Logic 141 (3):429-436 (2006)
  Copy   BIBTEX

Abstract

We prove that the Cutting Plane proof system based on Gomory–Chvátal cuts polynomially simulates the lift-and-project system with integer coefficients written in unary. The restriction on the coefficients can be omitted when using Krajíček’s cut-free Gentzen-style extension of both systems. We also prove that Tseitin tautologies have short proofs in this extension

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2005.12.006

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 104,556

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Extension without cut.Lutz Straßburger - 2012 - Annals of Pure and Applied Logic 163 (12):1995-2007.
Relative efficiency of propositional proof systems: resolution vs. cut-free LK.Noriko H. Arai - 2000 - Annals of Pure and Applied Logic 104 (1-3):3-16.
Lower Bounds for cutting planes proofs with small coefficients.Maria Bonet, Toniann Pitassi & Ran Raz - 1997 - Journal of Symbolic Logic 62 (3):708-728.
A Cut-free Gentzen Formulation Of The Modal Logic S5.T. Braüner - 2000 - Logic Journal of the IGPL 8 (5):629-643.
Describing proofs by short tautologies.Stefan Hetzl - 2009 - Annals of Pure and Applied Logic 159 (1-2):129-145.
Proofs with monotone cuts.Emil Jeřábek - 2012 - Mathematical Logic Quarterly 58 (3):177-187.
Gentzen Calculi for the Existence Predicate.Matthias Baaz & Rosalie Iemhoff - 2006 - Studia Logica 82 (1):7-23.
Cutting planes, connectivity, and threshold logic.Samuel R. Buss & Peter Clote - 1996 - Archive for Mathematical Logic 35 (1):33-62.

Analytics

Added to PP
2013-12-31

Downloads
37 (#674,901)

6 months
19 (#159,155)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Resolution over linear equations and multilinear proofs.Ran Raz & Iddo Tzameret - 2008 - Annals of Pure and Applied Logic 155 (3):194-224.

Add more citations

References found in this work

Add more references