Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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 |
ID: 49828142