کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430223 | 687929 | 2014 | 15 صفحه PDF | دانلود رایگان |

• 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.
Journal: Journal of Computer and System Sciences - Volume 80, Issue 7, November 2014, Pages 1359–1373