8
$\begingroup$

In https://en.wikipedia.org/wiki/Geometric_complexity_theory it is mentioned that ".. Ketan Mulmuley believes the program, if viable, is likely to take about 100 years before it can settle the P vs. NP problem".

It seems to indicate that the only currently viable program could face serious obstacles.

What are some of the obstacles where the program could fail?

$\endgroup$
  • $\begingroup$ not sure what you mean by "the only currently viable program". you mean within GC or of all approaches for P vs NP? and by the way, resolving P vs NP is not the only measure of usefulness of this or other theories... all attacks on P vs NP have faced serious obstacles so far... $\endgroup$ – vzn Nov 29 '15 at 1:12
  • 1
    $\begingroup$ I do not think that this program is "only currently viable program". There are several viable programs and approaches, and GCT is one of them. In the recent years, we have seen beautiful advances in many of those programs. Ryan Williams' proof of ACC not contained in NEXP and the method of shifted partial derivatives are two examples that come to mind... $\endgroup$ – Or Meir Dec 1 '15 at 21:47
11
$\begingroup$

It depends what you count as "the GCT program."

  1. Consider the specific suggestion (GCT I, GCT II) to use the vanishing/nonvanishing of certain multiplicities in the orbit closures of the determinant and permanent to resolve the strong permanent versus determinant conjecture (i.e., that the permanent is not in the orbit closure of any polynomially larger determinant). In this case, it is possible that even if the conjecture is true, that this is not reflected in the vanishing/nonvanishing of multiplicities of irreps supported on these orbit closures. It is even possible that the conjecture is not reflected in the appropriate inequality of multiplicities. I should note that there are various forms of evidence that this shouldn't happen, but it has not yet been formally ruled out.

Note, however, that if instead of multiplicities you merely want a separating module, then the strong perm v det conjecture is true if and only if there exists a separating module.

  1. If your goal is the original permanent versus determinant conjecture, there is an earlier step in GCT, namely (as pointed out by chazisop) moving to the strong perm v det conjecture by considering the orbit closures. It is conceivable that the original permanent versus determinant conjecture is true but the strong version is false. However, this seems highly unlikely to me. Also, if this is the situation, then none of our current methods can even come close to resolving the perm v det conjecture, since they all currently work for the "strong"/"approximative"/"border-"/Zariski-closed version of whatever algebraic complexity statement they are proving.

  2. If your goal is not perm v det but Boolean $\mathsf{NP} \not\subseteq \mathsf{P/poly}$, there are additional claimed steps in GCT that have yet to be published. It is possible that one of these unpublished steps could fail as well, but obviously it is hard to comment on the details of mathematics one hasn't seen...

  3. [Potential failures of lower bounds in general, not specific to GCT.] GCT is currently aimed at nonuniform lower bounds; that is, even in the GCT approach to Boolean lower bounds, it is aimed at showing $\mathsf{NP} \not\subseteq \mathsf{P/poly}$. But of course, it is consistent with current theorems that $\mathsf{P} \neq \mathsf{NP}$ yet $\mathsf{NP} \subseteq \mathsf{P/poly}$. Of course, it's also technically possible that $\mathsf{P} = \mathsf{NP}$ and the perm v det conjecture is false!

However, let me point out that the GCT program as it currently exists still seems to me like the first thing to try. If it turns out that any one of (1)-(3) above actually doesn't work, it will mean that the perm v det conjecture (and hence, $\mathsf{P}$ versus $\mathsf{NP}$) is almost unimaginably harder than we currently think it is. (It may be worth noting that this statement is coming from someone who already thinks that the following analogy may be roughly correct, if not inadequate: $\mathsf{P} \neq \mathsf{NP}$ is to our current state of knowledge as the Classification of Finite Simple Groups is to Fermat's Little Theorem). And even if that is the case, understanding the exact way in which the failure occurs will likely be important to making further progress.

$\endgroup$
  • 2
    $\begingroup$ It will nice if the notes $3.$ on $\mathsf{NP\not\subseteq P/poly}$ is released. Many more researchers would be able to comment as this is the version that mostly is studied (not counting algebraic perm vs det version). $\endgroup$ – Turbo Nov 28 '15 at 6:54
  • $\begingroup$ could you comment on "..I should note that there are various forms of evidence" in $1.$? $\endgroup$ – Turbo Nov 28 '15 at 7:06
5
$\begingroup$

I believe the "100 years" statement refers that the theory is general, but requires deep understanding and new results in representation theory and algebraic geometry to progress, something that might be slow to progress (I want to make a comparison to number theory, but I am not sure how apt it is).

Also, there is a loss of precision when translating to the algebro-geometric world: Instead of proving a lower bound against the properties of a complexity class (i.e. polynomials that vanish when objects in that class are given as input), you are proving it against its Zariski closure (of aforementioned polynomials). It is conceivable that in order to separate the two, one has to examine the boundary of that closure (those polynomials that occur only in the closure but on the original set). It is believed that in the determinant vs permanent variant of the GCT program, this is likely the case.

Finally from personal experience, the skillset required to understand GCT in depth is quite different than what is usually the focus of undergraduate or even master programs in CS, essentially picking up the prerequisites is a natural follow-up of choosing to study GCT.

$\endgroup$
  • $\begingroup$ No there seems to be some obstacles that could null the program.. it is a possible path not necessarily founded on correct ingredients 'as of now' $\endgroup$ – Turbo Nov 27 '15 at 8:00
  • $\begingroup$ I would say the second one has the potential to be such an obstacle, but it is very difficult to answer this question precisely. Imagine for example asking the same question for the same question for the P vs NP problem in general, before the barriers of relativization, natural proofs and algebrization were known. I suppose I included the other two parts because the "100 years" statement always seemed a bit arbitrary to me Joshua Grochow is both very knowledgeable in GCT and uses cstheory. I would be very interested to see an answer from him. $\endgroup$ – chazisop Nov 27 '15 at 8:06

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.