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 (of any of these systems and with any coefficients).

Original languageEnglish
Pages (from-to)429-436
Number of pages8
JournalAnnals of Pure and Applied Logic
Volume141
Issue number3
DOIs
StatePublished - 1 Sep 2006

    Scopus subject areas

  • Logic

    Research areas

  • Integer programming, Propositional proof complexity

ID: 49828142