AN OVERVIEW OF MATHEMATICAL ISSUES ARISING IN THE GEOMETRIC COMPLEXITY THEORY APPROACH TO VP not equal VNP Academic Article

abstract

• We discuss the geometry of orbit closures and the asymptotic behavior of Kronecker coefficients in the context of the geometric complexity theory program to prove a variant of Valiant's algebraic analogue of the P = NP conjecture. We also describe the precise separation of complexity classes that their program proposes to demonstrate. 2011 Society for Industrial and Applied Mathematics.

authors

• Landsberg, Joseph

published proceedings

• SIAM JOURNAL ON COMPUTING

author list (cited authors)

• Buergisser, P., Landsberg, J. M., Manivel, L., & Weyman, J.

citation count

• 43

complete list of authors

• Buergisser, Peter||Landsberg, JM||Manivel, Laurent||Weyman, Jerzy

publication date

• January 2011

publisher

• Society for Industrial & Applied Mathematics (SIAM)  Publisher

published in

• SIAM Journal on Computing  Journal

keywords

• Determinant
• Geometric Complexity Theory
• Geometric Invariant Theory
• Kronecker Coefficient
• Orbit Closure
• P Vs. Np
• Permanent

Digital Object Identifier (DOI)

• 10.1137/090765328

start page

• 1179

end page

• 1209

volume

• 40

issue

• 4

URL

• http://dx.doi.org/10.1137/090765328