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

<p>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. </p>

<p>There is a well known<a href="http://dx.doi.org/10.1137/0212043">1</a> 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)$.</p>

<p>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.</p>

<p><strong>Disclaimer</strong>: 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.</p>

<p><a href="http://dx.doi.org/10.1137/0212043">1</a> L. G. Valiant, S. Skyum, S. Berkowitz, C. Rackoff. <a href="http://dx.doi.org/10.1137/0212043">Fast parallel computation of polynomials using few processors</a>. SIAM J. Comput. 12(4), pp. 641-644, 1983.</p>

CC BY-SA 2.5
2010-11-01T17:00:06.223Z
is it the algebraic non-uniform equivalent of $NC^2 \neq NP$ or $NC^2 \neq \# P$?
Joshua Grochow
CC BY-SA 2.5
2010-11-01T19:02:18.763Z
@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
CC BY-SA 2.5
2010-12-23T13:00:35.660Z
Valiant et al. result works for any field.
Iddo Tzameret
CC BY-SA 2.5
2010-11-01T14:09:38.163Z
2010-12-23T12:48:02.927Z
2010-12-23T12:48:02.927Z
MassimoLauria
<p><em>Assuming the generalized Riemann hypothesis</em> (GRH), the following quite strong connections are known between $ VP= VNP $ and the collapse of the polynomial hierarchy ($ {\rm PH}$):</p>

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

<p>These are results from: Peter Burgisser, "<a href="http://dx.doi.org/10.1016/S0304-3975%2899%2900183-8">Cook’s versus Valiant’s hypothesis</a>",  Theor. Comp. Sci., 235:71–88,
2000.</p>

<p>See also: Burgisser, "<a href="http://math-www.uni-paderborn.de/agpb/work/habil.ps">Completeness and Reduction in Algebraic Complexity Theory</a>", 1998.</p>

CC BY-SA 4.0
2021-04-16T07:46:42.990Z
@IddoTzameret Would P=PSPACE or P=PP or BPP=PP imply VP=VNP?
Turbo
CC BY-SA 2.5
2010-12-23T00:44:03.123Z
I think you meant that $VP = VNP$ implies the collapse of the polynomial hierarchy, not that $VP \neq VNP$ implies this.
Robin Kothari
CC BY-SA 2.5
2010-12-22T15:42:03.407Z
2010-12-23T12:18:10.347Z
2010-12-23T12:18:10.347Z
Iddo Tzameret
<p>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.</p>

CC BY-SA 2.5
2010-08-24T23:15:28.070Z
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).
didest
CC BY-SA 2.5
2010-08-24T22:47:34.947Z
2010-11-01T16:01:52.723Z
2010-11-01T16:01:52.723Z
Moritz
<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2013-04-05T16:00:27.387Z
The monograph "Completeness and Reduction in Algebraic Complexity Theory" by Peter Bürgisser (math-www.uni-paderborn.de/agpb/work/habil.ps) may give you a better idea about the question.
Mahdi Cheraghchi
CC BY-SA 3.0
2014-11-14T17:39:19.547Z
Just updating Michaël's URL: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:V#vnp
András Salamon
CC BY-SA 4.0
2022-01-05T10:21:56.177Z
Another update for the zoo link: https://complexityzoo.net/Complexity_Zoo:V#vnp
et_l
CC BY-SA 2.5
2010-08-24T22:05:02.577Z
AFAIK, the Zoo gives all the known information.
http://qwiki.stanford.edu/wiki/Complexity_Zoo:V#vnp
Michaël Cadilhac
<cc.complexity-theory><complexity-classes><algebraic-complexity><conditional-results><gct>
Does $VP \neq VNP$ imply $P \neq NP$?
Benno
# Does $VP \neq VNP$ imply $P \neq NP$?

(Asked by: username_0 on 2010-08-24)

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?

**Tags:** cc.complexity-theory, complexity-classes, algebraic-complexity, conditional-results, gct

> **Comments:**
> **username_4**: AFAIK, the Zoo gives all the known information. http://qwiki.stanford.edu/wiki/Complexity_Zoo:V#vnp  
> **username_1**: The monograph "Completeness and Reduction in Algebraic Complexity Theory" by Peter Bürgisser (math-www.uni-paderborn.de/agpb/work/habil.ps) may give you a better idea about the question.  
> **username_2**: Just updating Michaël's URL: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:V#vnp  
> **username_3**: Another update for the zoo link: https://complexityzoo.net/Complexity_Zoo:V#vnp  

---

## 3 answers

### Answer by username_10 on 2010-08-24. Score: 28 | Accepted answer

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.

> **Comments:**
> **username_11**: 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).  

---

### Answer by username_7 on 2010-12-22. Score: 25

*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](http://dx.doi.org/10.1016/S0304-3975%2899%2900183-8)", Theor. Comp. Sci., 235:71–88,
2000.

See also: Burgisser, "[Completeness and Reduction in Algebraic Complexity Theory](http://math-www.uni-paderborn.de/agpb/work/habil.ps)", 1998.

> **Comments:**
> **username_9**: I think you meant that $VP = VNP$ implies the collapse of the polynomial hierarchy, not that $VP \neq VNP$ implies this.  
> **username_8**: @IddoTzameret Would P=PSPACE or P=PP or BPP=PP imply VP=VNP?  

---

### Answer by username_5 on 2010-11-01. Score: 16

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 known[1](http://dx.doi.org/10.1137/0212043) 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](http://dx.doi.org/10.1137/0212043) L. G. Valiant, S. Skyum, S. Berkowitz, C. Rackoff. [Fast parallel computation of polynomials using few processors](http://dx.doi.org/10.1137/0212043). SIAM J. Comput. 12(4), pp. 641-644, 1983.

> **Comments:**
> **username_6**: is it the algebraic non-uniform equivalent of $NC^2 \neq NP$ or $NC^2 \neq \# P$?  
> **username_5**: @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.  
> **username_7**: Valiant et al. result works for any field.  

---

