TY - JOUR

T1 - Computational complexity, Newton polytopes, and Schubert polynomials

AU - Adve, Anshul

AU - Robichaux, Colleen

AU - Yong, Alexander

N1 - Publisher Copyright:
© 2019, Seminaire Lotharingien de Combinatoire. All Rights Reserved.

PY - 2019

Y1 - 2019

N2 - 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 ∩ 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 × 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).

AB - 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 ∩ 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 × 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).

KW - Newton polytopes

KW - Schubert polynomials

KW - computational complexity

UR - http://www.scopus.com/inward/record.url?scp=85161431376&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85161431376&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85161431376

SN - 1286-4889

JO - Seminaire Lotharingien de Combinatoire

JF - Seminaire Lotharingien de Combinatoire

IS - 82

M1 - #52

ER -