Sparse Sets, Lowness and Highness
Sparse Sets, Lowness and Highness
复制标题
稀疏集、低度和高度
DOI：
10.1137/0215053
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
U. Schöning
中科院分区：
文献类型：
--
作者：
J. Balcázar;R. V. Book;U. Schöning
我们为pH（多项式层次结构的联合）和“广义殿下”的“广义lowness”开发了“广义”。这些音符的任意集。在pH值中，在两个情况下，每个稀疏集都延长了。多项式时间层次结构无限地扩展了许多级别。
We develop the notions of “generalized lowness” for sets in PH (the union of the polynomial-time hierarchy) and of “generalized highness” for arbitrary sets. Also, we develop the notions of “extended lowness” and “extended highness” for arbitrary sets. These notions extend the decomposition of NP into low sets and high sets developed by Schoning [15] and studied by Ko and Schoning [9].We show that either every sparse set in PH is generalized high or no sparse set in PH is generalized high. Further, either every sparse set is extended high or no sparse set is extended high. In both situations, the former case corresponds to the polynomial-time hierarchy having only finitely many levels while the latter case corresponds to the polynomial-time hierarchy extending infinitely many levels.