کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662474 1633550 2006 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Several notes on the power of Gomory–Chvátal cuts
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Several notes on the power of Gomory–Chvátal cuts
چکیده انگلیسی

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).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 141, Issue 3, September 2006, Pages 429-436