#####
Séminaire Lotharingien de Combinatoire, 82B.52 (2019), 12 pp.

# Anshul Adve, Colleen Robichaux, and Alexander Yong

# Computational complexity, Newton polytopes, and Schubert polynomials

**Abstract.**
The *nonvanishing* problem asks if a coefficient of a polynomial is nonzero. Many families of polynomials in algebraic combinatorics admit combinatorial counting rules and simultaneously enjoy having *saturated Newton polytopes* (SNP). Thereby, in amenable cases, *nonvanishing* is in the complexity class (NP intersection coNP) of problems with "good characterizations". This suggests a new algebraic combinatorics viewpoint on complexity theory.
This paper focuses on the case of *Schubert polynomials*. These form a basis of all polynomials and appear in the study of cohomology rings of flag manifolds. We give a tableau criterion for *nonvanishing*, 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, together with a theorem of A. Fink, K. Mészáros, and A. St. Dizier (2018), which proved a conjecture of C. Monical, N. Tokcan, and the third author (2017).

Received: November 15, 2018.
Accepted: February 17, 2019.
Final version: April 1, 2019.

The following versions are available: