کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427986 686586 2009 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A simplified way of proving trade-off results for resolution
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A simplified way of proving trade-off results for resolution
چکیده انگلیسی

We present a greatly simplified proof of the length-space trade-off result for resolution in [P. Hertel, T. Pitassi, Exponential time/space speedups for resolution and the PSPACE-completeness of black-white pebbling, in: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS '07), Oct. 2007, pp. 137–149], and also prove a couple of other theorems in the same vein. We point out two important ingredients needed for our proofs to work, and discuss some possible conclusions. Our key trick is to look at formulas of the type F=G∧H, where G and H are over disjoint sets of variables and have very different length-space properties with respect to resolution.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 109, Issue 18, 31 August 2009, Pages 1030-1035