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

Citation
Kd. Mulmuley et M. Sohoni, Geometric complexity theory I: An approach to the P vs. NP and related problems, SIAM J COMP, 31(2), 2001, pp. 496-526
Citations number
46
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
496 - 526
Database
ISI
SICI code
0097-5397(20011011)31:2<496:GCTIAA>2.0.ZU;2-8
Abstract
We suggest an approach based on geometric invariant theory to the fundament al 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 stabilit y in geometric invariant theory due to Mumford[Geometric Invariant Theory, Springer-Verlag, Berlin, 1965]. Then we reduce fundamental lower bound prob lems in complexity theory to problems concerning infinitesimal neighborhood s of the orbits of partially stable points. We also suggest an approach to tackle the latter class of problems via construction of explicit obstructio ns.