  We prove the existence of signed combinatorial interpretations for several
large families of structure constants. These families include standard bases of
symmetric and quasisymmetric polynomials, as well as various bases in Schubert
theory. The results are stated in the language of computational complexity,
while the proofs are based on the effective M\"obius inversion.
