Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version)
Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version)
复制标题
通过 Oracle 分离多项式时间层次结构（初步版本）
DOI：
--
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
A. Yao
中科院分区：
文献类型：
--
作者：
A. Yao
我们提出了指数下界的深度-k布尔电路计算某些功能的大小。这些结果意味着存在一个预言集A，使得相对于A，多项式时间层次中的所有级别都是不同的，即，对于所有的k，kP，A适当地包含在k+1 P，A中。
We present exponential lower bounds on the size of depth-k Boolean circuits for computing certain functions. These results imply that there exists an oracle set A such that, relative to A, all the levels in the polynomial-time hierarchy are distinct, i.e., ΣkP,A is properly contained in Σk+1P,A for all k.