# Littlewood-Richardson rule for the complete flag variety: GapP complete?

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?

• Don't you want to explain, what is the problem? – Sasha Mar 12 '16 at 19:26
• @Sasha added an explicit statement of the problem. – Matt Samuel Mar 12 '16 at 20:03
• Is it about complete flags in type A, or in arbitrary Dynkin type? – Sasha Mar 12 '16 at 20:08
• @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. – Matt Samuel Mar 12 '16 at 20:13
• Isn't this question essentially asking about the status of a well-known open problem? – Sam Hopkins Mar 13 '16 at 4:40