P versus NP and geometry
Preprint
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.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- The stabilizer of immanantsLinear Algebra and its Applications, 2011
- Nonvanishing of Kronecker coefficients for rectangular shapesAdvances in Mathematics, 2011
- Characterizing Valiant's algebraic complexity classesJournal of Complexity, 2008
- P, NP and mathematics – a computational complexity perspective2007
- Construction and classification of complex simple Lie algebras via projective geometrySelecta Mathematica, 2002
- Completeness and Reduction in Algebraic Complexity Theory2000
- On linear preservers of immanantsLinear Algebra and its Applications, 1996
- A note on the determinant and permanent problemInformation and Computation, 1990
- Dimer problem in statistical mechanics-an exact resultPhilosophical Magazine, 1961