For the setting of decision problems, Impagliazzo et al. implicitly showed the following equivalence: Randomized polynomial-time decision procedures can be simulated in NSUBEXP (the subexponential version of NP) with subpolynomial advice on infinitely many input lengths if and only if NEXP is not in P/poly. We establish a full analogue in the setting of verification procedures: Arthur-Merlin games can be simulated in Σ2SUBEXP (the subexponential version of Σ2P) with subpolynomial advice on infinitely many input lengths if and only if Σ2EXP is not in NP/poly.
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 Σ2P, we show that