On the Complexity of the Membership Problem for Moment Polytopes

We show that the problem of deciding membership in the moment polytope associated with a representation of a compact connected Lie group is in NP and coNP. These polytopes characterize the asymptotic non-vanishing of representation-theoretic multiplicities, including the stretched Kronecker coefficients. In contrast, it has recently been shown that deciding positivity of a single Kronecker coefficient is NP-hard in general [Ikenmeyer, Mulmuley and Walter, arXiv:1507.02955]. Thus our result suggests that representation theory can be easier in the asymptotic regime. It also has implications on the complexity of the marginal problem in quantum physics. This is joint work with P. Buergisser, M. Christandl and K. Mulmuley.