Record Details

Geometric complexity theory I: An approach to the P vs. NP and related problems

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Geometric complexity theory I: An approach to the P vs. NP and related problems
 
Creator MULMULEY, KD
SOHONI, M
 
Subject invariant theory
determinant
varieties
geometric invariant theory
computational complexity
algebraic geometry
representation theory
stability
 
Description We suggest an approach based on geometric invariant theory to the fundamental lower bound problems in complexity theory concerning formula and circuit size. Specifically, we introduce the notion of a partially stable point in a reductive-group representation, which generalizes the notion of stability in geometric invariant theory due to Mumford[Geometric Invariant Theory, Springer-Verlag, Berlin, 1965]. Then we reduce fundamental lower bound problems in complexity theory to problems concerning infinitesimal neighborhoods of the orbits of partially stable points. We also suggest an approach to tackle the latter class of problems via construction of explicit obstructions.
 
Publisher SIAM PUBLICATIONS
 
Date 2011-08-29T05:10:54Z
2011-12-26T12:58:25Z
2011-12-27T05:48:19Z
2011-08-29T05:10:54Z
2011-12-26T12:58:25Z
2011-12-27T05:48:19Z
2001
 
Type Article
 
Identifier SIAM JOURNAL ON COMPUTING, 31(2), 496-526
0097-5397
http://dx.doi.org/10.1137/S009753970038715X
http://dspace.library.iitb.ac.in/xmlui/handle/10054/11970
http://hdl.handle.net/10054/11970
 
Language en