תקציר
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 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - ספט׳ 2006 |
פורסם באופן חיצוני | כן |