8
$\begingroup$

GCT purports to provide a program to show that $NP \not \subset P/poly$.

  1. At the high level what are the steps involved in the program and what stage is each step in?

  2. What difficulties currently are known or envisioned to be roadblocks and what are the easy targets?

$\endgroup$
  • $\begingroup$ You mean separating $NP$ from $P/poly$, not $P$ from $P/poly$. $\endgroup$ – Erfan Khaniki Aug 31 '17 at 11:31
  • $\begingroup$ @ErfanKhaniki yes........... $\endgroup$ – 1.. Aug 31 '17 at 11:32
  • 2
    $\begingroup$ In addition to the nice answer by Christian you check the related question mathoverflow.net/questions/277408/… $\endgroup$ – Abdelmalek Abdesselam Aug 31 '17 at 13:22
  • 2
    $\begingroup$ The CS Theory StackExchange site may be a better place for this question. A near-duplicate of the present question has already been posted there: cstheory.stackexchange.com/questions/17610/… $\endgroup$ – Timothy Chow Aug 31 '17 at 15:00
11
$\begingroup$

First off, GCT is usually stated as a way of showing that $NP \not \subset P/poly$, which would imply that $P \neq NP$. This strategy was proposed by Mulmuley and several collaborators in a series of papers Geometric complexity theory I-VIII. These papers and several survey articles are available on Mulmuley's website.

  1. The first step in the program would be to separate the arithmetic circuit classes $VP$ and $VNP$ (here we think of families of circuits with arithmetic gates which formally compute a family of polynomials in their input variables). This is the arithmetic analogue of the weaker $\#P \not \subset NC$ conjecture. The determinant $\Delta_m$ and permanent $\Omega_n$ polynomials are complete for $VP$ and $VNP$ respectively. Therefore, to separate these classes, it suffices to show that the determinental complexity (the smallest $m$ such that a padded version of $\Omega_n(y)$ can be expressed as the determinant of an $m \times m$ matrix whose entries are affine linear combinations of the entries of the variables $y$) of the permanent is superpolynomial. The main idea is to compare the coordinate rings $A:=\mathbb{C}[\overline{GL_m \cdot \Delta_m}]$ and $B:=\mathbb{C}[\overline{GL_m \cdot z^{m-n}\Omega_n}]$ as $GL_m$-reps. In order to show that $\overline{GL_m \cdot \Delta_m}$ does not contain the (padded) permanent, it suffices to show that there is no surjective map of $GL_m$-reps. from $A \to B$. The idea here is to give labels $\lambda$ of irreps. appearing in $B$ but not in $A$, precluding such a map. To get from here to the boolean result $\#P \not \subset NC$, the idea is the transfer this result (done over $\mathbb{C}$) to finite fields. Mulmuley mentions in several places that the details of this plan are to be sketched in a future paper (GCT IX?), which, as far as I know, is not yet available.

This strategy is really only a simpler version of the the strategy for the main problem (although the weaker result would still be one of the most impressive in the history of complexity theory). Mulmuley has identified more complicated polynomials to take the place of the determinant and permanent in the $NP \not \subset P/poly$ version, and the strategy there is analogous.

  1. The hoped-for "easy" target was that there would be some irrep. $V_{\lambda}$ appearing in $B$, but not appearing at all in $A$. This has been ruled out in this paper by Burgisser, Ikenmeyer, and Panova. Thus we are left with the more difficult route of being able to estimate (nonzero) multiplicities of irreps. in $A$ and $B$ well enough to preclude the map. This gets into several famous open problems in algebraic combinatorics: how to give positive formulas for Kronecker and plethysm coefficients. Even if these difficulties are surmounted, we are a long way from $P \neq NP$, but separating $VP$ and $VNP$ would itself be an extremely impressive result.
| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Is there any linear programming and integer programming problems that GCT talks about as need to be solved? $\endgroup$ – 1.. Aug 31 '17 at 11:22
  • $\begingroup$ @777 Possibly there are some smaller programming problems hidden in the eventual details, but it is thought (see Mulmuley's description of the "flip theorem") that the representation theoretic obstructions are the tools which get over the fundamental difficulty of the complexity-theoretic problems. $\endgroup$ – Christian Gaetz Aug 31 '17 at 11:25

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.