کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436722 690030 2006 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Simplifying the weft hierarchy
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Simplifying the weft hierarchy
چکیده انگلیسی

We give simple, self-contained proofs of the basic hardness results for the classes W[t] of the weft hierarchy. We extend these proofs to higher levels of the hierarchy and illuminate the distinctions among its classes. The anti-monotone collapse at W[1,s] and the normalization of weft-t formulas arise as by-products of the proofs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 351, Issue 3, 28 February 2006, Pages 303-313