PH的一种复杂性类分解

J4 ›› 2012, Vol. 34 ›› Issue (9): 184-187.

PH的一种复杂性类分解

李雅瑞

( 桂林空军学院,广西桂林 541003)

收稿日期:2012-04-12 修回日期:2012-06-25 出版日期:2012-09-25 发布日期:2012-09-25

A Complexity Decomposition of the PolynomialTime Hierarchy

LI Yarui

(Guilin Air Force Academy,Guilin 541003,China)

Received:2012-04-12 Revised:2012-06-25 Online:2012-09-25 Published:2012-09-25

摘要/Abstract

摘要：

本文基于 ΔPK复杂性类给出多项式时间谱系PH 的一个分解，并讨论了相关的一些性质。利用该分解给出PH 是否只有有限个层次这一重要计算复杂性理论问题的两个充分条件,并证明了NP中稀疏集构成的语言类在LP2∧中。

关键词: 多项式时间谱系, &Delta, PK复杂性类, 图灵机

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

Key words: polynomialtime hierarchy;ΔPKcomplexity classes;Turing machine

李雅瑞. PH的一种复杂性类分解[J]. J4, 2012, 34(9): 184-187.

LI Yarui. A Complexity Decomposition of the PolynomialTime Hierarchy[J]. J4, 2012, 34(9): 184-187.