New Collapse Consequences of NP Having Small Circuits
New Collapse Consequences of NP Having Small Circuits
复制标题
具有小电路的 NP 的新崩溃后果
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
O. Watanabe
中科院分区：
文献类型：
--
作者：
J. Köbler;O. Watanabe
我们表明，如果一个可自我还原的集合具有多项式大小的电路，那么对于概率类ZPP（NP）而言，它的含量很低。假设NP具有多项式大小的回路，这在Karp，Lipton和Sipser（1980）的众所周知的结果上表明，pH值在同一假设下的第二级σ2p进一步的结果，我们在诸如UP，很少P和C = P之类的复杂性类别具有多项式大小的电路之类的假设下得出了新的崩溃后果。
We show that if a self-reducible set has polynomial-size circuits, then it is low for the probabilistic class ZPP(NP). As a consequence we get a deeper collapse of the polynomial-time hierarchy PH to ZPP(NP) under the assumption that NP has polynomial-size circuits. This improves on the well-known result of Karp, Lipton, and Sipser (1980) stating a collapse of PH to its second level σ 2 P under the same assumption. As a further consequence, we derive new collapse consequences under the assumption that complexity classes like UP, FewP, and C=P have polynomial-size circuits.