摘要
本文基于ΔPK-复杂性类给出多项式时间谱系PH的一个分解,并讨论了相关的一些性质。利用该分解给出PH是否只有有限个层次这一重要计算复杂性理论问题的两个充分条件,并证明了NP中稀疏集构成的语言类在LP2∧中。
It is discussed that a complexity resolution of the Polynomial-time Hierarchy based on the △PK - complexity classes. Regarding that whether the polynomial-time Hierarchy has only finite levels or not, its two A conditions are given. It is proved that the language classes constructed by sparse sets in NP is in LA2P .
出处
《计算机工程与科学》
CSCD
北大核心
2012年第9期184-187,共4页
Computer Engineering & Science
