科研之友
微信
新浪微博
Facebook
分享链接
摘要
In several settings, derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are known to imply it, i.e., whether the ability to derandomize in any way implies the ability to do so in the canonical way through pseudorandom generators. For the setting of decision problems, Impagliazzo, Kabanets, and Wigderson (2002) implicitly showed the following equivalence: Randomized polynomial-time decision procedures for promise problems can be simulated in NSUBEXP (the subexponential version of NP) with subpolynomial advice on infinitely many input lengths if and only if NEXP not subset of P/poly. We establish a full analog in the setting of verification procedures: Arthur-Merlin games for promise problems can be simulated in Sigma 2SUBEXP (the subexponential version of Sigma P-2) with subpolynomial advice on infinitely many input lengths if and only if Sigma 2EXP not subset of 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 Sigma P-2, we show that (i)PSPACE subset of Np/poly implies PSPACE subset of Sigma P-2 and (ii) coNP subset of NP/poly implies PH subset of P-2(Sigma)P. Of possible independent interest is a generic framework that we provide, which captures several results in the literature of the form "derandomization implies circuit lower bounds." In particular, our framework enables a unified view of our result, the one by Impagliazzo et al. (2002) mentioned above, as well as the result by Kabanets and Impagliazzo (2004) that derandomizing polynomial identity testing yields arithmetic circuit lower bounds.
- 出版日期2017-3
