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