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\cap coNP$ of problems with "good characterizations". This suggests a new algebraic combinatorics viewpoint on complexity theory. This report discusses 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\'{e}sz\'{a}ros, and A. St. Dizier, which proved a conjecture of C. Monical, N. Tokcan, and the third author.
翻译:无损问题询问多元合成系数是否为非零。 许多在代数组合组合组合体中的多元合成家庭接受组合计数规则,并同时享受饱和牛顿多面形(SNP) 。 因此,在可处理的案例中,非损耗是“良好特性”问题的复杂类别$NP\cap coNP$。 这表明对复杂理论有一种新的代数组合学观点。 本报告讨论了舒伯特多面体的情况。 这些是所有多元模型的基础,并出现在旗帜形体的共振环研究中。 我们给出了非损耗的平板标准, 我们从中推算出第一个多面时间算法。 这些结果来自苏比特普的新定性, 一种对nx n 网形中任何子组定义的超面相色谱的概括化, 以及A. Fink, K. M\'quenciviels, 和 A. D. C. C. C. 和 A. S. C. 和 A. A. S. Can.