  Schubert polynomials form a basis of all polynomials and appear in the study
of cohomology rings of flag manifolds. The vanishing problem for Schubert
polynomials asks if a coefficient of a Schubert polynomial is zero. We give a
tableau criterion to solve this problem, from which we deduce the first
polynomial time algorithm. These results are obtained from new
characterizations of the Schubitope, a generalization of the permutahedron
defined for any subset of the n x n grid. In contrast, we show that computing
these coefficients explicitly is #P-complete.
