Seberapa sulitkah menggunakan pendekatan GCT Mulmuley-Sohoni untuk menunjukkan pemisahan kompleksitas yang diketahui?

Dalam posting tamu ini oleh Josh Grochow di weblog kompleksitas dia melaporkan pada lokakarya baru-baru ini yang didedikasikan untuk GCT yang diadakan di Princeton pada bulan Juli. Beberapa peserta berpendapat bahwa kita harus menggunakan GCT untuk menyerang masalah yang lebih mudah daripada vs. $\mathsf{P}$ untuk membangun intuisi dan melihat apakah metode tersebut memiliki potensi.$\mathsf{NP}$

Pertanyaan yang telah menggangguku:

Apakah mungkin menggunakan GCT untuk menunjukkan pemisahan yang diketahui seperti atau L ≠ P S P A C E ?$\mathsf{P} \neq \mathsf{EXP}$$\mathsf{L} \neq \mathsf{PSPACE}$

Apakah sesuatu seperti $\mathsf{L} \neq \mathsf{PSPACE}$

1. Bahkan tidak masuk akal dalam konteks GCT, atau
2. Benar-benar sepele dan tidak menarik dalam kerangka kerja GCT, atau
3. Mengarah ke dugaan sekeras vs N P ?$\mathsf{P}$$\mathsf{NP}$

Jawaban singkat: mungkin tidak (1), jelas tidak (2), dan mungkin (3).

$L$$P$$PSPACE$$EXP$

$FP \neq FEXP$ -- is probably incredibly difficult in a GCT approach, since that would require the use of modular representation theory (representation theory over finite fields), which is not well understood in any context.

But a reasonable goal might be to use GCT to prove an algebraic analog of $FP \neq FEXP$.

To get to your question: I believe that these questions can be formulated in a GCT context, though it's not immediately obvious how. More or less, you need a function that is complete for the class and characterized by its symmetries; extra bonus if the representation theory associated to the function is easy to understand, but this latter is usually quite difficult.

Even once the questions are formulated in a GCT context, I have no idea how difficult it will be to use GCT to prove (algebraic analogs of) $FP \neq FEXP$ etc. The representation-theoretic conjectures that will arise in these contexts will likely have a very similar flavor to the ones arising in $P$ vs $NP$ or permanent vs determinant. One might hope that the classical proofs of these separation results might give some idea of how to find the representation-theoretic "obstructions" needed for a GCT proof. However, the proofs of the statements you mention are all hierarchy theorems based on diagonalization, and I do not see how diagonalization will really give you much insight into the representation theory associated with a function that is complete for (the algebraic analog of) $FEXP$, say. On the other hand, I haven't yet seen how to formulate $FEXP$ in a GCT context, so it's a little early to say.

Finally, as I mentioned in that blog post, Peter Burgisser and Christian Ikenmeyer have attempted to re-prove the lower bound on the border-rank of $2 \times 2$ matrix multiplication (which was proven to be 7 in 2006 by Joseph Landsberg). They were able to show the border-rank is at least 6 by a computer search for GCT obstructions. Update April 2013: they have since managed to re-prove Landsberg's result using a GCT obstruction, and to show an asymptotic $\frac{3}{2}n^2 - 2$ lower bound on matrix multiplication using such obstructions. Although GCT has not so far reproduced the known lower bound on matrix multiplication, it does enable a computer search more efficient than the alternative (which would involve Grobner bases, which are doubly-exponential time in the worst case). In their talks at the workshop, both Peter and Christian pointed out (correctly, I'd say) that what we really hope to get of computing small examples is not re-proving known lower bounds, but some insight that will let us use these techniques to prove new lower bounds.

The nice thing about GCT in the context of matrix multiplication is that the technique easily generalizes from $2 \times 2$ to $3 \times 3$ matrix multiplication (although computing the obstructions with the current techniques obviously gets more expensive), whereas Landsberg's approach seems very difficult to implement even for the $3 \times 3$ case. A similar thing could be said about the complexity class separations you mention: GCT is general enough that it may apply not only to known results like $FP \neq FEXP$, but also to unknown ones like $P \neq NP$, whereas we know diagonalization does not.

There's a new paper on the arXiv by Joshua Grochow, which shows how to put several known lower bound techniques into the GCT framework and seems like it answers your question somewhat.

(This is mostly just a comment, but no one would notice a comment so I'm posting it as an answer.)

Unifying and generalizing known lower bounds via geometric complexity theory

Joshua A. Grochow

We show that most arithmetic circuit lower bounds and relations between lower bounds naturally fit into the representation-theoretic framework suggested by geometric complexity theory (GCT), including: the partial derivatives technique (Nisan-Wigderson), the results of Razborov and Smolensky on $AC^0[p]$, multilinear formula and circuit size lower bounds (Raz et al.), the degree bound (Strassen, Baur-Strassen), the connected components technique (Ben-Or), depth 3 arithmetic circuit lower bounds over finite fields (Grigoriev-Karpinski), lower bounds on permanent versus determinant (Mignon-Ressayre, Landsberg-Manivel-Ressayre), lower bounds on matrix multiplication (B\"{u}rgisser-Ikenmeyer) (these last two were already known to fit into GCT), the chasms at depth 3 and 4 (Gupta-Kayal-Kamath-Saptharishi; Agrawal-Vinay; Koiran), matrix rigidity (Valiant) and others. That is, the original proofs, with what is often just a little extra work, already provide representation-theoretic obstructions in the sense of GCT for their respective lower bounds. This enables us to expose a new viewpoint on GCT, whereby it is a natural unification and broad generalization of known results. It also shows that the framework of GCT is at least as powerful as known methods, and gives many new proofs-of-concept that GCT can indeed provide significant asymptotic lower bounds. This new viewpoint also opens up the possibility of fruitful two-way interactions between previous results and the new methods of GCT; we provide several concrete suggestions of such interactions. For example, the representation-theoretic viewpoint of GCT naturally provides new properties to consider in the search for new lower bounds.