Wednesday, 15 January 2014

computational complexity - Does EXP $in$ P/poly imply NP=RP?

Note that it would suffice to prove $EXP subseteq P/poly$ implies $NP = BPP$ (since the latter implies $NP = RP$).



I am pretty sure this is not known. $NP neq RP$ does not seem to imply any circuit lower bounds for $EXP$.



Note that $EXP subseteq P/poly$ does imply $P neq NP$. If $EXP subseteq P/poly$ then there is some fixed $k$ for which $TIME[2^n]$ has $n^k$-size circuits. Therefore $P subseteq TIME[2^n]$ has $n^k$-size circuits. But $P = NP$ implies that $Sigma_2 P = P$, and we know by Kannan's theorem that $Sigma_2 P$ does not have $n^k$-size circuits for any fixed $k$ -- this is a contradiction. (This result is due to Meyer, cited in the famous Karp-Lipton paper.)



I would suspect that one can prove $EXP subseteq P/poly$ implies $RP neq NP$ or maybe $ZPP neq NP$, but the above proof doesn't do the job. (Technically, since I believe $EXP notsubseteq P/poly$, the negation should imply everything...)

No comments:

Post a Comment