Derandomizing Arthur–Merlin Games using Hitting Sets
Derandomizing Arthur–Merlin Games using Hitting Sets
复制标题
DOI：
10.1007/s00037-005-0197-7
复制
发表时间：
1999-10
影响因子：
1.4
通讯作者：
Peter Bro Miltersen;N. V. Vinodchandran
中科院分区：
文献类型：
--
作者：
Peter Bro Miltersen;N. V. Vinodchandran
我们证明了AM(以及图的非同构)在NP中。如果对于某些ε>；0，某些语言在∩中需要大小为2εn的不确定回路，这改进了Arvind和Köbler以及Klivans和van Melkebeek的结果，他们证明了同样的结论，但在更强的困难假设下。相反，我们的方法是基于Andreev，Clementi和Rolim的去随机化的击中集方法的加强。作为衍生结果，我们证明了这种方法足够强大，可以很容易地证明以下蕴含的含义：对于某些ε>；0，如果E中有一种语言需要大小为2εn的不确定电路，则P=bpp。这与Imagliazzo和Wigderson的定理“只”不同，因为它用非确定性电路代替了确定性电路。
We prove thatAM(and hence Graph Nonisomorphism) is inNPif for some ε > 0, some language inNE∩coNErequires nondeterministic circuits of size 2εnThis improves results of Arvind and Köbler and of Klivans and van Melkebeek who proved the same conclusion, but under stronger hardness assumptions.The previous results on derandomizingAMwere based on pseudorandom generators. In contrast, our approach is based on a strengthening of Andreev, Clementi and Rolim’s hitting set approach to derandomization. As a spin-off, we show that this approach is strong enough to give an easy proof of the following implication: for some ε > 0, if there is a language inEwhich requires nondeterministic circuits of size 2εn, thenP = BPP. This differs from Impagliazzo and Wigderson’s theorem “only” by replacing deterministic circuits with nondeterministic ones.