Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games
Barış Aydınlıoğlu, Dieter van Melkebeek · 2012
Hardness against nondeterministic circuits is known to suffice for derandomizing Arthur-Merlin games. We show a result in the other direction - that hardness against nondeterministic circuits is *necessary* for derandomizing Arthur-Merlin games. In fact, we obtain an equivalence for a mild notion of derandomization: Arthur-Merlin games can be simulated in Sigma_2-SUBEXP (the sub exponential version of Sigma_2-P) with sub polynomial advice on infinitely many input lengths if and only if Sigma_2-E} (the linear-exponential version of Sigma_2-P) requires nondeterministic circuits of super polynomial size on infinitely many input lengths. Our equivalence result represents a full analogue of a similar result by Impagliazzo et al. in the deterministic setting: Randomized polynomial-time decision procedures can be simulated in NSUBEXP (the sub exponential version of NP) with sub polynomial advice on infinitely many input lengths if and only if NE (the linear-exponential version of NP) requires deterministic circuits of super polynomial size on infinitely many input lengths. A key ingredient in our proofs is improved Karp-Lipton style collapse results for nondeterministic circuits. The following are two instantiations that may be of independent interest: Assuming that Arthur-Merlin games can be derandomized in Sigma_2-P, we show that (i) PSPACE in NP/poly implies PSPACE in Sigma_2-P, and (ii) coNP in NP/poly implies PH in P^\Sigma_2-P.