Perfect correspondences between dot-depth and polynomial-time hierarchies

作者：

Highlights：

• 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.

摘要

•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.

论文关键词：Computational complexity,Leaf-languages,Polynomial-time hierarchy,Dot-depth hierarchy

论文评审过程：Received 25 September 2006, Revised 11 March 2014, Accepted 18 March 2014, Available online 25 March 2014.

论文官网地址：https://doi.org/10.1016/j.jcss.2014.03.006