Record Details

Geometric complexity theory II: Towards explicit obstructions for embeddings among class varieties

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Geometric complexity theory II: Towards explicit obstructions for embeddings among class varieties
 
Creator MULMULEY, KD
SOHONI, M
 
Subject algebraic-groups
computational complexity
algebraic geometry
representation theory
geometric invariant theory
 
Description In [K. D. Mulmuley and M. Sohoni, SIAM J. Comput., 31 (2001), pp. 496 - 526], henceforth referred to as Part I, we suggested an approach to the P vs. NP and related lower bound problems in complexity theory through geometric invariant theory. In particular, it reduces the arithmetic (characteristic zero) version of the NP not subset of P conjecture to the problem of showing that a variety associated with the complexity class NP cannot be embedded in a variety associated with the complexity class P. We shall call these class varieties associated with the complexity classes P and NP. This paper develops this approach further, reducing these lower bound problems - which are all nonexistence problems - to some existence problems: specifically to proving the existence of obstructions to such embeddings among class varieties. It gives two results towards explicit construction of such obstructions. The first result is a generalization of the Borel-Weil theorem to a class of orbit closures, which include class varieties. The second result is a weaker form of a conjectured analogue of the second fundamental theorem of invariant theory for the class variety associated with the complexity class NC. These results indicate that the fundamental lower bound problems in complexity theory are, in turn, intimately linked with explicit construction problems in algebraic geometry and representation theory. The results here were announced in [K. D. Mulmuley and M. Sohoni, in Advances in Algebra and Geometry (Hyderabad, 2001), Hindustan Book Agency, New Delhi, India, 2003, pp. 239 - 261].
 
Publisher SIAM PUBLICATIONS
 
Date 2011-08-29T05:13:43Z
2011-12-26T12:58:25Z
2011-12-27T05:48:19Z
2011-08-29T05:13:43Z
2011-12-26T12:58:25Z
2011-12-27T05:48:19Z
2008
 
Type Article
 
Identifier SIAM JOURNAL ON COMPUTING, 38(3), 1175-1206
0097-5397
http://dx.doi.org/10.1137/080718115
http://dspace.library.iitb.ac.in/xmlui/handle/10054/11971
http://hdl.handle.net/10054/11971
 
Language en