# Does $VP \neq VNP$ imply $P \neq NP$?

As far as I understand, the geometric complexity theory program attempts to separate $VP \neq VNP$ by proving that the permament of a complex-valued matrix is much harder to compute than the determinant.

The question I had after skimming through the GCT Papers: Would this immediately imply $P \neq NP$, or is it merely a major step towards this goal?

The short answer is 'no'. No such implication is known. There are two main obstacles: Going from arithmetic circuit complexity to boolean complexity (VP≠VNP implies P/poly≠NP/poly) and then going from boolean circuit complexity (P/poly≠NP/poly) to uniform complexity (P≠NP). Neither of these steps is known. I believe that P/poly≠NP/poly implies VP≠VNP, however.

• Your last sentence is true: if there is a field where VP=VNP then P/poly=NP/poly (follow the link in Cadilhac's comment). – Diego de Estrada Aug 24 '10 at 23:15

Assuming the generalized Riemann hypothesis (GRH), the following quite strong connections are known between $VP= VNP$ and the collapse of the polynomial hierarchy (${\rm PH}$):

1. If $VP= VNP\,$ (over any field) then the polynomial hierarchy collapses to the second level;
2. If $VP=VNP\,$ over a field of characteristic $0$, then $\rm{NC}^3/{\rm poly}={\rm P}/{\rm poly} = {\rm PH}/{\rm poly}$;
3. If $VP=VNP\,$ over a field of finite characteristic $p$, then $\rm{NC}^2/{\rm poly}={\rm P}/{\rm poly} = {\rm PH}/{\rm poly}$.

These are results from: Peter Burgisser, "Cook’s versus Valiant’s hypothesis", Theor. Comp. Sci., 235:71–88, 2000.

• I think you meant that $VP = VNP$ implies the collapse of the polynomial hierarchy, not that $VP \neq VNP$ implies this. – Robin Kothari Dec 23 '10 at 0:44

I can give you an informal reason for why the separation would not prove $P \ne NP$.

VP and VNP focus on algebraic functions which degree is bounded by a polynomial. Notice that it is easy to compute in an algebraic function of exponential degree with a polynomial size algebraic circuit.

There is a well known1 depth reduction for algebraic circuits: any polynomial size algebraic circuit computing a polynomial of degree $d$ can be turned into an algebraic circuit of polynomial size and depth $O(\log d \log n)$.

You may think of $VP$ as an algebraic variant of $NC^2$, thus proving that $VP \ne VNP$ amounts to prove an algebraic non-uniform equivalent of $NC^2 \ne \# P$. That would not rule out $P = NP$, at least not immediately.

Disclaimer: I can't access the paper right now and I don't remember if the reduction works in any field or just in finite ones.

1 L. G. Valiant, S. Skyum, S. Berkowitz, C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM J. Comput. 12(4), pp. 641-644, 1983.

• is it the algebraic non-uniform equivalent of $NC^2 \neq NP$ or $NC^2 \neq \# P$? – Joshua Grochow Nov 1 '10 at 17:00
• @JoshuaGrochow: you are right, and I fixed it. While $VNP$ is considered the moral equivalent of $NP$, it is in fact more close to the spirit of $\# P$. In fact the share complete problems. – MassimoLauria Nov 1 '10 at 19:02
• Valiant et al. result works for any field. – Iddo Tzameret Dec 23 '10 at 13:00