P versus NP and geometry Academic Article

abstract

• 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.

authors

• Landsberg, Joseph

published proceedings

• JOURNAL OF SYMBOLIC COMPUTATION

author list (cited authors)

• Landsberg, J. M.

citation count

• 1

complete list of authors

• Landsberg, JM

publication date

• December 2010

publisher

• Elsevier  Publisher

keywords

• Determinant
• Geometric Complexity Theory
• Grassmannian
• Holographic Algorithms
• NP
• P
• Permanent
• Spinor

Digital Object Identifier (DOI)

• 10.1016/j.jsc.2010.06.015

start page

• 1359

end page

• 1377

volume

• 45

issue

• 12

URL

• http://dx.doi.org/10.1016/j.jsc.2010.06.015