文章基本信息

标题：Several notes on the power of Gomory-Chvatal cuts
本地全文：下载
作者：Edward Hirsch ; Arist Kojevnikov
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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).
关键词：cutting plane , propositional proof , Tsetin tautologies