کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427434 | 686504 | 2010 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover–Delayer games
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover–Delayer games A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover–Delayer games](/preview/png/427434.png)
چکیده انگلیسی
In this note we show that the asymmetric Prover–Delayer game developed in Beyersdorff et al. (2010) [2] for Parameterized Resolution is also applicable to other tree-like proof systems. In particular, we use this asymmetric Prover–Delayer game to show a lower bound of the form 2Ω(nlogn)2Ω(nlogn) for the pigeonhole principle in tree-like Resolution. This gives a new and simpler proof of the same lower bound established by Iwama and Miyazaki (1999) [7] and Dantchev and Riis (2001) [5].
Research highlights
► New asymmetric Prover–Delayer game for lower bounds in free-like proof systems.
► Refines the Prover–Delayer Game of Pudlak and Impagliazzo.
► New simple proof of the optimal lower bound for the pigeonhole principle.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 110, Issue 23, 15 November 2010, Pages 1074–1077
Journal: Information Processing Letters - Volume 110, Issue 23, 15 November 2010, Pages 1074–1077
نویسندگان
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria,