36
$\begingroup$

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?

$\endgroup$
27
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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). $\endgroup$ – Diego de Estrada Aug 24 '10 at 23:15
21
$\begingroup$

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.

See also: Burgisser, "Completeness and Reduction in Algebraic Complexity Theory", 1998.

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

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.

$\endgroup$
  • 2
    $\begingroup$ is it the algebraic non-uniform equivalent of $NC^2 \neq NP$ or $NC^2 \neq \# P$? $\endgroup$ – Joshua Grochow Nov 1 '10 at 17:00
  • $\begingroup$ @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. $\endgroup$ – MassimoLauria Nov 1 '10 at 19:02
  • 2
    $\begingroup$ Valiant et al. result works for any field. $\endgroup$ – Iddo Tzameret Dec 23 '10 at 13:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.