Generic separations
Generic separations
复制标题
通用分离
DOI：
10.1109/sct.1994.315809
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
T. Yamakami
中科院分区：
文献类型：
--
作者：
L. Fortnow;T. Yamakami
M.Blum和R.Imagliazzo(Proc.第28届IEEE计算机科学基础研讨会，第118-126页，1987)，使用Hartmanis和hemachandra(1991)和Rackoff(1982)的技术，表明如果P=NP，则P(G)=NP(G)/SPL Cap/co-NP(G)=Up(G)，其中G是通用的先知。他们留下了一个悬而未决的问题，即这些坍塌是否发生在多项式时间层次的更高级别。我们对这个问题给出了一个令人惊讶的否定答案。我们证明了对于任何一般预言G，对于任何k/Spl Ges/2，在U/Spl Deltasub ksup P/(G)/Spl capspl Pisub ksup P/(G)中存在计数集，但在/SPL Deltasub ksup P/(G)中不存在计数集。一个直接的推论是，通用甲骨文将/SPL Sigmasub ksup Pspl Capspl Pisub ksup P/和/SPL Deltasub ksup P/分开。我们还证明了相关结果对第二类复杂性也成立。
M. Blum and R. Impagliazzo (Proc. 28th IEEE Symposium on Foundations of Computer Science, pp. 118-126, 1987), using techniques of Hartmanis and Hemachandra (1991) and Rackoff (1982), showed that if P = NP then P(G) = NP(G)/spl cap/co-NP(G) = UP(G), where G is a generic oracle. They left open the question as to whether these collapses occur at higher levels of the polynomial-time hierarchy. We give a surprising negative answer to this question. We show that relative to any generic oracle G and for any k/spl ges/ 2, there exists a tally set in U/spl Deltasub ksup P/(G)/spl capspl Pisub ksup P/(G) but not in /spl Deltasub ksup P/(G). An immediate corollary is that generic oracles separate /spl Sigmasub ksup Pspl capspl Pisub ksup P/ and /spl Deltasub ksup P/. We also show that related results hold for type-2 complexity.<<ETX>>