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

Abstract

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

139 pages. Corrects error in the conjectural saturation hypothesis (SH) in the earlier version, which was pointed out in a recent paper of Briand et al (arXIv:0810.3163v1 [math.CO])

References in corpus (7)

• Honeycombs and sums of Hermitian matrices
• Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH
• Geometric Complexity Theory VII: Nonstandard quantum group for the plethysm problem
• Geometric Proofs of Horn and Saturation Conjectures
• Geometric Complexity Theory V: On deciding nonvanishing of a generalized Littlewood-Richardson coefficient
• Geometric Complexity Theory VIII: On canonical bases for the nonstandard quantum groups
• An Invitation to the Generalized Saturation Conjecture

Cited by in corpus (19)

• The stability of the Kronecker products of Schur functions
• Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH
• Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
• An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP
• On the complexity of computing Kronecker coefficients
• Kronecker products, characters, partitions, and the tensor square conjectures
• Membership in moment polytopes is in NP and coNP
• Witten non abelian localization for equivariant K-theory, and the [Q,R]=0 theorem
• Geometric Complexity Theory VII: Nonstandard quantum group for the plethysm problem
• Permanent versus determinant: not via saturations
• Report on "Geometry and representation theory of tensors for computer science, statistics and other areas."
• Geometric Complexity Theory VIII: On canonical bases for the nonstandard quantum groups
• Multiplicity of compact group representations and applications to Kronecker coefficients
• Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
• The partition algebra and the Kronecker coefficients
• On P vs. NP, Geometric Complexity Theory, and the Flip I: a high level view
• On the growth of the Kronecker coefficients
• Geometric Complexity Theory: Introduction
• Constructive Separations and Their Consequences