摘要：We prove that AM (and hence Graph Nonisomorphism) is in NP if for some epsilon > 0, some language in NE intersection coNE requires nondeterministic circuits of size 2^(epsilon n). This improves recent results of Arvind and K¨obler and of Klivans and Van Melkebeek who proved the same conclusion, but under stronger hardness assumptions, namely, either the existence of a language in NE intersection coNE which cannot be approximated by nondeterministic circuits of size less than 2^(epsilon n) or the existence of a language in NE intersection coNE which requires oracle circuits of size 2^(epsilon n) with oracle gates for SAT (satisfiability). The previous results on derandomizing AM were 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 (if the existence of explicit dispersers can be assumed known) proof of the following implication: For some epsilon > 0, if there is a language in E which requires nondeterministic circuits of size 2^(epsilon n), then P=BPP. This differs from Impagliazzo and Wigderson's theorem "only" by replacing deterministic circuits with nondeterministic ones.
