Atlas Mathematical Conference Abstracts || Conferences | Abstracts | for Organizers | About AMCA

Second St.Petersburg Days of Logic and Computability
August 24-26, 2003
Petersburg Department of Steklov Institute of Mathematics
St. Petersburg, Russia

Organizers
Sergei ADIAN (Russia), Sergei ARTEMOV (Russia/USA), Nikolai KOSSOVSKI (Russia), Maurice MARGENSTERN (France), Grigori MINTS (USA), Yuri MATIYASEVICH (Russia), the chairman, Nikolai NAGORNY (Russia), Vladimir OREVKOV (Russia), Anatol SLISSENKO (France)

View Abstracts
Conference Homepage

Several Notes on the Power of Gomory-Chvatal Cuts
by
Edward A. Hirsch
Steklov Institute of Mathematics at St.Petersburg
Coauthors: Arist Kojevnikov (St.Petersburg State University)

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 coefficients can be omitted when using Krajícek'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).

Date received: March 14, 2003

Copyright © 2003 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # cajy-08.