Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds

Abstract

We show that if Arthur-Merlin protocols can be derandomized, then there is a language computable in deterministic exponential-time with access to an NP oracle that requires circuits of exponential size. More formally, if every promise problem in prAM, the class of promise problems that have Arthur-Merlin protocols, can be computed by a deterministic polynomial-time algorithm with access to an NP oracle, then there is a language in ENP that requires circuits of size Ω(2n/n). The lower bound in the conclusion of our theorem suffices to construct pseudorandom generators with exponential stretch. We also show that the same conclusion holds if the following two related problems can be computed in polynomial time with access to an NP-oracle: (i) approximately counting the number of accepted inputs of a circuit, up to multiplicative factors; and (ii) recognizing an approximate lower bound on the number of accepted inputs of a circuit, up to multiplicative factors. © 2011 Springer Basel AG.