کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874121 1441024 2018 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Relating size and width in variants of Q-resolution
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Relating size and width in variants of Q-resolution
چکیده انگلیسی
We continue the investigation begun in [6] into the application of this technique to proof systems for quantified Boolean formulas. We demonstrate a relationship between the size of proofs in level-ordered Q-Resolution and the width of proofs in Q-Resolution. In general, however, the picture is not positive, and for most stronger systems based on Q-Resolution, the size-width relation of [3] fails, answering an open question from [6].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 138, October 2018, Pages 1-6
نویسندگان
, ,