The cohomology ring of a complete flag variety $X$ has a basis of Schubert classes $S_u$ for permutations $u$. Define the Littlewood-Richardson coefficient $c_{uv}^w$ for permutations $u,v,w$ to be the coefficient of $S_w$ in the expansion of $S_uS_v$ in terms of the basis. The problem is to compute $c_{uv}^w$ given $u,v,w$.

I (and others) have found some formulas for Littlewood-Richardson coefficients in the complete flag variety that show that the problem is in GapP, meaning it is the difference of two #P problems. Despite decades of effort, no one has yet found a formula that shows the problem is in #P (i.e. a Littlewood-Richardson rule). I've tried on and off for 9 years myself.

This would make sense if the problem were complete for the complexity class GapP; it is widely believed that $\mathrm{GapP}^+\neq\#\mathrm P$, where $\mathrm{GapP}^+$ is the set of GapP problems where the result is positive, which would imply that no Littlewood-Richardson rule exists. Is it known whether the problem is GapP-complete?

  • $\begingroup$ Don't you want to explain, what is the problem? $\endgroup$ – Sasha Mar 12 '16 at 19:26
  • $\begingroup$ @Sasha added an explicit statement of the problem. $\endgroup$ – Matt Samuel Mar 12 '16 at 20:03
  • $\begingroup$ Is it about complete flags in type A, or in arbitrary Dynkin type? $\endgroup$ – Sasha Mar 12 '16 at 20:08
  • $\begingroup$ @Sasha my GapP formula works for all types, including infinite-dimensional Kac-Moody, so it doesn't matter, but I would guess even in type A alone it would be complete for the complexity class. $\endgroup$ – Matt Samuel Mar 12 '16 at 20:13
  • $\begingroup$ Isn't this question essentially asking about the status of a well-known open problem? $\endgroup$ – Sam Hopkins Mar 13 '16 at 4:40

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.