Geometric complexity theory (GCT) is an approach via algebraic geometry and representation theory towards the P vs. NP problems and related problems Ketan D. Mulmuley.

More precisely, the idea is to solve permanent vs. determinant problems over some field $K$. Solving this problem $K = \mathbb{F}_p$ for large enough $p$ implies very hard computational complexity problem #P$\not\subset$NC.

However nowadays GCT deals only with permanent vs. determinant problem for $\mathbb{C}$, as I know. Ketan D. Mulmuley explained the reason: The arithmetic case is easier than the case when $K = \mathbb{F}_p$ because it avoids complications in algebra that arise in the case of finite fields

I completely argee with this argument, however I do not think that this is a reason do not consider finite fields now at all.

My question is: does somebody try to develop GCT for $\overline{\mathbb{F}_p}$?

I think the first step in this direction should be a classification of Weyl modules over finite fields. Is it done?

UPD: In On P vs. NP, Geometric Complexity Theory, and The Flip I: a high-level view, Technical Report TR-2007-13, computer science department, The University of Chicago, September, 2007. Mulmuley writes In [GCT11], the problems that arise in the context of the flip over an algebraically closed field of positive characteristic, or a finite field are discussed.

However GCT11 does not published yet...

  • $\begingroup$ The fact that the representation theory of reductive groups is not semisimple in positive characteristic is a huge barrier. $\endgroup$ – W. Cadegan-Schlieper Jan 28 '17 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.