5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ There's a related question on implications between VP vs VNP and P vs NP, but it doesn't address your more specific questions about GCT. $\endgroup$ – Robert Andrews Mar 31 at 15:16
  • $\begingroup$ yes, that's precisely why i am asking this question $\endgroup$ – Nift Mar 31 at 20:58
3
$\begingroup$

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 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 (equivalently, HWV obstruction, see Bürgisser-Ikenmeyer STOC '13, arXiv) must exist.

$\endgroup$

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.