38
$\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$
4

3 Answers 3

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$
1
  • 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$
    – didest
    Aug 24, 2010 at 23:15
25
$\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$
2
  • 1
    $\begingroup$ I think you meant that $VP = VNP$ implies the collapse of the polynomial hierarchy, not that $VP \neq VNP$ implies this. $\endgroup$ Dec 23, 2010 at 0:44
  • $\begingroup$ @IddoTzameret Would P=PSPACE or P=PP or BPP=PP imply VP=VNP? $\endgroup$
    – Turbo
    Apr 16, 2021 at 7:46
16
$\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$
3
  • 2
    $\begingroup$ is it the algebraic non-uniform equivalent of $NC^2 \neq NP$ or $NC^2 \neq \# P$? $\endgroup$ Nov 1, 2010 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$ Nov 1, 2010 at 19:02
  • 2
    $\begingroup$ Valiant et al. result works for any field. $\endgroup$ Dec 23, 2010 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.