Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry

摘要: This article belongs to a series on geometric complexity theory (GCT), an approach the P vs. NP and related problems through algebraic geometry representation theory. The basic principle behind this is called flip. In essence, it reduces negative hypothesis in (the lower bound problems), such as problem characteristic zero, positive upper problems): specifically, showing that of deciding nonvanishing fundamental structural constants geometry, well known plethysm constants--or rather certain relaxed forms these decision probelms--belong class P. article, we suggest plan for implementing flip, i.e., belong based reduction preceding complexity-theoretic hypotheses mathematical positivity hypotheses: there exist formulae--i.e. formulae with nonnegative coefficients--for under consideration functions associated them. These turn out be intimately similar properties Kazhdan-Lusztig polynomials multiplicative canonical (global crystal) bases Drinfeld-Jimbo quantum groups. proofs depend Riemann over finite fields results. Thus here, conjunction says validity conjecture zero linked problems.