کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430223 687929 2014 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Perfect correspondences between dot-depth and polynomial-time hierarchies
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Perfect correspondences between dot-depth and polynomial-time hierarchies
چکیده انگلیسی


• Introduction of polynomial-time tree reducibility (ptt-reducibility).
• Correspondence between ptt-reducibility and inclusions between complexity classes.
• The first levels of the dot-depth hierarchy are closed under ptt-reducibility.
• Gap theorem of leaf-language definability above the Boolean closure of NP.

We introduce the polynomial-time tree reducibility (ptt-reducibility) for formal languages. Our main result establishes a one–one correspondence between this reducibility and inclusions between complexity classes. More precisely, for languages B and C it holds that B ptt-reduces to C if and only if the unbalanced leaf-language class of B is robustly contained in the unbalanced leaf-language class of C. Formerly, such correspondence was only known for balanced leaf-language classes. Moreover, we show that restricted to regular languages, the levels 0, 1/2, 1, and 3/2 of the dot-depth hierarchy are closed under ptt-reducibility. Our results also have applications in complexity theory: We obtain the first gap theorem of leaf-language definability above the Boolean closure of NP.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 80, Issue 7, November 2014, Pages 1359–1373
نویسندگان
, , ,