| PH的一种复杂性类分解 |
| |
| 引用本文： | 李雅瑞.PH的一种复杂性类分解[J].计算机工程与科学,2012,34(9):184-187. |
| |
| 作者姓名： | 李雅瑞 |
| |
| 作者单位： | 桂林空军学院,广西桂林,541003 |
| |
| 摘 要： | 本文基于ΔPK-复杂性类给出多项式时间谱系PH的一个分解,并讨论了相关的一些性质。利用该分解给出PH是否只有有限个层次这一重要计算复杂性理论问题的两个充分条件,并证明了NP中稀疏集构成的语言类在LP2∧中。
|
| 关 键 词： | 多项式时间谱系 ΔPK-复杂性类 图灵机 |
A Complexity Decomposition of the Polynomial-Time Hierarchy |
| |
| LI Ya-rui.A Complexity Decomposition of the Polynomial-Time Hierarchy[J].Computer Engineering & Science,2012,34(9):184-187. |
| |
| Authors: | LI Ya-rui |
| |
| Affiliation: | LI Ya-rui (Guilin Air Force Academy,Guilin 541003,China) |
| |
| Abstract: | 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 conditions are given.It is proved that the language classes constructed by sparse sets in NP is in LP2∧. |
| |
| Keywords: | polynomial-time hierarchy ΔPK-complexity classes Turing machine |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 |
|
点击此处可从《计算机工程与科学》下载全文 |
|
