In this primarily expository article, I describe geometric approaches to variants of P versus NP, present several results that illustrate the role of group actions in complexity theory, and make a first step towards geometric definitions of complexity classes. My goal is to help bring geometry and complexity theory closer together. © 2010 Elsevier Ltd.
- Geometric Complexity Theory
- Holographic Algorithms