کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437897 | 690204 | 2015 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Quasipolynomial size proofs of the propositional pigeonhole principle
ترجمه فارسی عنوان
اثبات اندازه کواسیولینومالی اصل گوسفند گویا
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی اثبات، اثبات پیشنهادی، اصل کبوتر، فرگه اثبات، فرایندهای پیشرفته
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Cook and Reckhow proved in 1979 that the propositional pigeonhole principle has polynomial size extended Frege proofs. Buss proved in 1987 that it also has polynomial size Frege proofs; these Frege proofs used a completely different proof method based on counting. This paper shows that the original Cook and Reckhow extended Frege proofs can be formulated as quasipolynomial size Frege proofs. The key point is that st-connectivity can be used to define the Cook–Reckhow construction.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 576, 20 April 2015, Pages 77–84
Journal: Theoretical Computer Science - Volume 576, 20 April 2015, Pages 77–84
نویسندگان
Sam Buss,