Hello, this is beta version of diophantus. If you want to report about a mistake, please, write to
hello@diophantus.org
pdf
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.
Reviews
There are no reviews yet.
Comments
Log in to leave a comment.
Reviews
There are no reviews yet.
Log in to leave a review.
There are no comments yet.