1

According to the answers in posting it is possible that $\mathsf{VP} = \mathsf{VNP}$ and $\mathsf{P} \neq \mathsf{NP}$ are simultaneously correct.

$\mathsf{VP} = \mathsf{VNP}$ implies $\mathsf{P/poly} = \mathsf{PH/poly}$ (assuming the Generalized Riemann Hypothesis). This means that $\mathsf{VP} = \mathsf{VNP}$ would amplify the power of polynomial circuits even if $\mathsf{P} \neq \mathsf{NP}$.

The best known obstruction for $\mathsf{P} \neq \mathsf{BPP}$ comes from circuit related issue for problems in $\mathsf{E}$. However if circuits have more power which is the scenario posed by $\mathsf{VP}=\mathsf{VNP}$, may be the obstruction for $\mathsf{P} \neq \mathsf{BPP}$ is not legitimate anymore.

How does $\mathsf{VP} = \mathsf{VNP}$ amplify the power of randomness?

If $\mathsf{VP} = \mathsf{VNP}$ were truth then is $\mathsf{P}\neq \mathsf{BPP}=\mathsf{NP}$ most likely scenario?

Are other possibilities such as $$(1)\mbox{ }\mathsf{P}=\mathsf{BPP}\neq \mathsf{NP}\quad \quad(2)\mbox{ }\mathsf{P}=\mathsf{BPP}=\mathsf{NP}\quad\quad(3)\mbox{ }\mathsf{P}\neq\mathsf{BPP}\neq\mathsf{NP}$$ least likely?

Are there any reasons to believe or not believe so?

Community
  • 1
  • The answer you linked says $NP \notin P/poly$ implies $VP \neq VNP$. The contrapositive is $VP = VNP$ implies $P = NP$? – Nikhil Sep 18 '15 at 01:54
  • 3
    @Nikhil: Not quite: the contrapositive is that $\mathsf{NP} \subseteq \mathsf{P/poly}$, which implies $\mathsf{\Sigma_2 P} = \mathsf{\Pi_2 P}$ (Karp-Lipton). The implication in your last sentence is not known. – Joshua Grochow Sep 18 '15 at 03:08
  • @Kaveh It is not just conjectured. It is known. look at posts there. Please make modification. –  Sep 18 '15 at 05:39
  • ok if you think that is better. I am thinking in stronger terms that $2$ may not be even possible and that $1$ is the likely outcome if $VP=VNP$ holds –  Sep 18 '15 at 05:46
  • Are you interested in whether randomness can help NP (as stated), or whether randomness can help solve NP problems (which I think is what you mean based on the rest of the question)? The question of whether "randomness can help NP" sounds more to me like AM vs NP than like NP vs BPP. The question of whether randomness can help solve NP problems sounds to me like BPP vs NP. – Joshua Grochow Sep 18 '15 at 14:58
  • 3
    @JoshuaGrochow: Oops! of course you are right! Or $O_2^p$ actually! :-) (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.136.7013) – Nikhil Sep 18 '15 at 17:00
  • @Nikhil: I knew about $\mathsf{S_2 P}$, but not about $\mathsf{O_2 P}$ - great reference, thanks! – Joshua Grochow Sep 18 '15 at 19:35
  • @JoshuaGrochow I am wondering whether $BPP=NP$ holds if $VP=VNP$ holds. Both are unconventional scenarios. I am interested in penultimate line. "I am thinking $(1)$ is likely possibility and other possibilities such as $(2)$ is unlikely if $\mathsf{VP}=\mathsf{VNP}$". –  Sep 18 '15 at 20:29

0 Answers0