Membership in moment polytopes is in NP and coNP

Understand

We show that the problem of deciding membership in the moment polytope associated with a finite-dimensional unitary representation of a compact, connected Lie group is in NP and coNP.

• This is the first non-trivial result on the computational complexity of this problem, which naively amounts to a quadratically-constrained program.
• Our result applies in particular to the Kronecker polytopes, and therefore to the problem of deciding positivity of 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].