1
$\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?

Improve this question
$\endgroup$
8
  • $\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, 2015 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, 2015 at 3:08
  • $\begingroup$ @Kaveh It is not just conjectured. It is known. look at posts there. Please make modification. $\endgroup$
    – user34945
    Sep 18, 2015 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, 2015 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, 2015 at 17:00

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.