کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10118843 1633557 2005 26 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Separation results for the size of constant-depth propositional proofs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Separation results for the size of constant-depth propositional proofs
چکیده انگلیسی
We define a general method to lift principles requiring exponential tree-size (d+12)-LK-refutations for d∈N to principles requiring exponential sequence-size d-LK-refutations, which will be described for the Ramsey principle and d=0. From this we also deduce width lower bounds for resolution refutations of the Ramsey principle.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 136, Issues 1–2, October 2005, Pages 30-55
نویسندگان
, ,