English

27 Pages

Downloading requires you to have access to the YouScribe library

__
Learn all about the services we offer
__

Description

Niveau: Supérieur, Master, Bac+5

ar X iv :0 90 7. 28 50 v1 [ cs .C C] 1 6 J ul 20 09 AN OVERVIEW OF MATHEMATICAL ISSUES ARISING IN THE GEOMETRIC COMPLEXITY THEORY APPROACH TO VP 6= VNP PETER BURGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN 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 analog of the P 6= NP conjecture. We also describe the precise separation of complexity classes that their program proposes to demonstrate. 1. Introduction In a series of papers [43, 44, 41, 42, 40, 38, 39, 37], K. Mulmuley and M. Sohoni outline an approach to the P v.s. NP problem, that they call the Geometric Complexity Theory (GCT) program. The starting point is Valiant's conjecture VP 6= VNP [56] (see also [58, 8]) which essentially says that the permanent hypersurface in m2 variables (i.e., the set of m?m matri- ces X with permm(X) = 0) cannot be realized as an affine linear section of the determinant hypersurface in n(m)2 variables with n(m) a polynomial function of m.

ar X iv :0 90 7. 28 50 v1 [ cs .C C] 1 6 J ul 20 09 AN OVERVIEW OF MATHEMATICAL ISSUES ARISING IN THE GEOMETRIC COMPLEXITY THEORY APPROACH TO VP 6= VNP PETER BURGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN 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 analog of the P 6= NP conjecture. We also describe the precise separation of complexity classes that their program proposes to demonstrate. 1. Introduction In a series of papers [43, 44, 41, 42, 40, 38, 39, 37], K. Mulmuley and M. Sohoni outline an approach to the P v.s. NP problem, that they call the Geometric Complexity Theory (GCT) program. The starting point is Valiant's conjecture VP 6= VNP [56] (see also [58, 8]) which essentially says that the permanent hypersurface in m2 variables (i.e., the set of m?m matri- ces X with permm(X) = 0) cannot be realized as an affine linear section of the determinant hypersurface in n(m)2 variables with n(m) a polynomial function of m.

- group slm2 ?
- polynomial vanishing
- group
- sπcm
- representation theory
- detn
- valiant's
- gln2 ·
- ring can

Subjects

Informations

Published by | rasum |

Reads | 17 |

Language | English |

Report a problem