P versus NP and geometry

2009/10/13 by Landsberg, J. M.
#Algebraic Geometry (math.AG) #Computational Complexity (cs.CC) #Differential Geometry (math.DG) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.0910.2443

Abstract

I describe three geometric approaches to resolving variants of P v. NP, present several results that illustrate the role of group actions in complexity theory, and make a first step towards completely geometric definitions of complexity classes.

Related

• On P vs. NP, Geometric Complexity Theory, and the Flip I: a high level view
• On P vs. NP, Geometric Complexity Theory, and the Riemann Hypothesis
• On P vs. NP, Geometric Complexity Theory, Explicit Proofs and the Complexity Barrier
• Geometric Complexity Theory: an introduction for geometers
• Report on "Mathematical Aspects of P vs. NP and its Variants."