0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The answer you linked says $NP \notin P/poly$ implies $VP \neq VNP$. The contrapositive is $VP = VNP$ implies $P = NP$? $\endgroup$ – Nikhil Sep 18 '15 at 1:54
  • 3
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Sep 18 '15 at 3:08
  • $\begingroup$ @Kaveh It is not just conjectured. It is known. look at posts there. Please make modification. $\endgroup$ – user34945 Sep 18 '15 at 5:39
  • $\begingroup$ 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 $\endgroup$ – user34945 Sep 18 '15 at 5:46
  • 3
    $\begingroup$ @JoshuaGrochow: Oops! of course you are right! Or $O_2^p$ actually! :-) (citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.136.7013) $\endgroup$ – Nikhil Sep 18 '15 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy