DOI

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).

Язык оригиналаанглийский
Страницы (с-по)429-436
Число страниц8
ЖурналAnnals of Pure and Applied Logic
Том141
Номер выпуска3
DOI
СостояниеОпубликовано - 1 сен 2006

    Предметные области Scopus

  • Логика

ID: 49828142