Super-bits, Demi-bits, and NP/qpoly-natural Proofs
Super-bits, Demi-bits, and NP/qpoly-natural Proofs
复制标题
超级比特、半比特和 NP/qpoly 自然证明
DOI：
10.1007/3-540-63248-4_8
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
S. Rudich
中科院分区：
文献类型：
--
作者：
S. Rudich
我们介绍了超位猜想，它允许发展的理论概括的伪随机性的概念，以便foolnon-deterministicstatistical测试。这种新的伪随机性排除了NP/poly的存在--这是一种可以对P/poly起作用的自然属性。这是P/poly-natural proofs [10]的原始理论的一个重要扩展。我们还介绍了密切相关的位猜想，这是更直观的，是有趣的开放问题的来源。
We introduce the super-bit conjecture, which allows the development of a theory generalizing the notion of pseudorandomness so as to foolnon-deterministicstatistical tests. This new kind of pseudo-randomness rules out the existence ofN P/poly-natural properties that can work againstP/poly. This is an important extension of the original theory ofP/poly-natural proofs [10]. We also introduce the closely related demi-bit conjecture which is more intuitive and is the source of interesting open problems.