<p>The short answer is no these are not known, though they are certainly not out of the question. There are no direct implications known to P vs NP, and we do not even have a conjecture (let alone theorem) that such-and-such a representation is an obstruction iff <span class="math-container">$VP \neq VNP$</span>.</p>
<p>One can start to get at an implication to ordinary P vs NP by trying to implement GCT in positive characteristic, using the polynomials from <a href="https://doi.org/10.1137/S009753970038715X" rel="nofollow noreferrer">GCT I</a> that more closely capture P/poly and NP. Since poly-size Boolean circuits are equivalent in power to poly-size algebraic circuits over a finite field, this would actually show NP not in P/poly. However, in positive characteristic both the geometry and the representation theory get harder (and it's not even clear if multiplicity is the right notion any more, because one is then dealing with modular representation theory, where representations need not be completely reducible).</p>
<p>Even in characteristic zero, we don't know the &quot;general converse&quot; about obstructions, namely, we don't know that <span class="math-container">$VP \neq VNP$</span> implies existence of multiplicity obstructions. But we do know that if <span class="math-container">$VNP \not\subseteq \overline{VP}$</span> then a <a href="http://dx.doi.org/10.1007/s00037-015-0103-x" rel="nofollow noreferrer">separating module</a> (equivalently, HWV obstruction, see <a href="https://doi.org/10.1145/2488608.2488627" rel="nofollow noreferrer">Bürgisser-Ikenmeyer STOC '13</a>, <a href="https://arxiv.org/abs/1210.8368" rel="nofollow noreferrer">arXiv</a>) must exist.</p>

CC BY-SA 4.0
2021-04-01T04:58:37.483Z
2021-04-01T04:58:37.483Z
Joshua Grochow
<p>Reading through various papers on geometric complexity theory (GCT), there is one thing, which pops up, while claimed in various places, that it is an approach to P vs NP, all the results seems to accumulate in conditional statements for VP vs VNP or NC vs #P. Are there any implications known, which connect the obstruction-based approach to VP vs VNP with P vs NP?</p>
<p>One more thing I keep wondering about is whether the attempts at separation through obstructions are strict, i.e. is there a class of obstructions, which exists if and only if <span class="math-container">$VP \neq VNP$</span>?</p>
<p>Note: I use P vs NP here in the precise sense of Cook's hypothesis, not in the sense of P v NP in fields of certain characteristic as it sometimes appears in GCT papers.</p>

CC BY-SA 4.0
2021-03-31T15:16:55.997Z
There's a [related question](https://cstheory.stackexchange.com/questions/529/does-vp-neq-vnp-imply-p-neq-np) on implications between VP vs VNP and P vs NP, but it doesn't address your more specific questions about GCT.
Robert Andrews
CC BY-SA 4.0
2021-03-31T20:58:32.237Z
yes, that's precisely why i am asking this question
Ilk
<p-vs-np><algebraic-complexity>
Questions about P vs NP and geometric complexity theory
Ilk
# Questions about P vs NP and geometric complexity theory

(Asked by: username_0 on 2021-03-31)

Reading through various papers on geometric complexity theory (GCT), there is one thing, which pops up, while claimed in various places, that it is an approach to P vs NP, all the results seems to accumulate in conditional statements for VP vs VNP or NC vs #P. Are there any implications known, which connect the obstruction-based approach to VP vs VNP with P vs NP?

One more thing I keep wondering about is whether the attempts at separation through obstructions are strict, i.e. is there a class of obstructions, which exists if and only if $VP \neq VNP$?

Note: I use P vs NP here in the precise sense of Cook's hypothesis, not in the sense of P v NP in fields of certain characteristic as it sometimes appears in GCT papers.

**Tags:** p-vs-np, algebraic-complexity

> **Comments:**
> **username_1**: There's a [related question](https://cstheory.stackexchange.com/questions/529/does-vp-neq-vnp-imply-p-neq-np) on implications between VP vs VNP and P vs NP, but it doesn't address your more specific questions about GCT.  
> **username_0**: yes, that's precisely why i am asking this question  

---

## 1 answers

### Answer by username_2 on 2021-04-01. Score: 3 | Accepted answer

The short answer is no these are not known, though they are certainly not out of the question. There are no direct implications known to P vs NP, and we do not even have a conjecture (let alone theorem) that such-and-such a representation is an obstruction iff $VP \neq VNP$.

One can start to get at an implication to ordinary P vs NP by trying to implement GCT in positive characteristic, using the polynomials from [GCT I](https://doi.org/10.1137/S009753970038715X) that more closely capture P/poly and NP. Since poly-size Boolean circuits are equivalent in power to poly-size algebraic circuits over a finite field, this would actually show NP not in P/poly. However, in positive characteristic both the geometry and the representation theory get harder (and it's not even clear if multiplicity is the right notion any more, because one is then dealing with modular representation theory, where representations need not be completely reducible).

Even in characteristic zero, we don't know the "general converse" about obstructions, namely, we don't know that $VP \neq VNP$ implies existence of multiplicity obstructions. But we do know that if $VNP \not\subseteq \overline{VP}$ then a [separating module](http://dx.doi.org/10.1007/s00037-015-0103-x) (equivalently, HWV obstruction, see [Bürgisser-Ikenmeyer STOC '13](https://doi.org/10.1145/2488608.2488627), [arXiv](https://arxiv.org/abs/1210.8368)) must exist.


---

