Before revision:  Second, we prove thatgiven a rational measure, an optimal transport to a set of measures can be computed in polynomial time . However, the complexity of this task depends on the size of an encoding of this measure, not only on the input size to the underlying barycenter problem. We show that this distinction causes a simple proof that SCMP is in NP to fail; whether SCMP is in NP remains open .
After revision:  Second, we prove thatgiven a rational measure, an optimal transport to a set of measures can be computed in polynomial time in the size of a bit encoding of the measure. However, the encoding size of a barycenter may be exponential in the encoding size of the underlying measures .