GEOMETRIC COMPLEXITY THEORY II: TOWARDS EXPLICIT OBSTRUCTIONS FOR EMBEDDINGS AMONG CLASS VARIETIES.
Saved in:
| Title: | GEOMETRIC COMPLEXITY THEORY II: TOWARDS EXPLICIT OBSTRUCTIONS FOR EMBEDDINGS AMONG CLASS VARIETIES. |
|---|---|
| Authors: | Mulmuley, Ketan D.1 mulmuley@cs.chicago.edu, Sohoni, Milind2 sohoni@cse.iitb.ernet.in |
| Source: | SIAM Journal on Computing. 2008, p1175-1206. 32p. |
| Subjects: | Geometry problems & exercises, Varieties (Universal algebra), Embeddings (Mathematics), Computational complexity, Algebraic geometry, Mathematical analysis, Geometric invariant theory |
| Abstract: | 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 ⊈ 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]. [ABSTRACT FROM AUTHOR] |
| Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 43480180 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: GEOMETRIC COMPLEXITY THEORY II: TOWARDS EXPLICIT OBSTRUCTIONS FOR EMBEDDINGS AMONG CLASS VARIETIES. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Mulmuley%2C+Ketan+D%2E%22">Mulmuley, Ketan D.</searchLink><relatesTo>1</relatesTo><i> mulmuley@cs.chicago.edu</i><br /><searchLink fieldCode="AR" term="%22Sohoni%2C+Milind%22">Sohoni, Milind</searchLink><relatesTo>2</relatesTo><i> sohoni@cse.iitb.ernet.in</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Computing%22">SIAM Journal on Computing</searchLink>. 2008, p1175-1206. 32p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Geometry+problems+%26+exercises%22">Geometry problems & exercises</searchLink><br /><searchLink fieldCode="DE" term="%22Varieties+%28Universal+algebra%29%22">Varieties (Universal algebra)</searchLink><br /><searchLink fieldCode="DE" term="%22Embeddings+%28Mathematics%29%22">Embeddings (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Algebraic+geometry%22">Algebraic geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+analysis%22">Mathematical analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Geometric+invariant+theory%22">Geometric invariant theory</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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 ⊈ 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]. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=43480180 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/080718115 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 32 StartPage: 1175 Subjects: – SubjectFull: Geometry problems & exercises Type: general – SubjectFull: Varieties (Universal algebra) Type: general – SubjectFull: Embeddings (Mathematics) Type: general – SubjectFull: Computational complexity Type: general – SubjectFull: Algebraic geometry Type: general – SubjectFull: Mathematical analysis Type: general – SubjectFull: Geometric invariant theory Type: general Titles: – TitleFull: GEOMETRIC COMPLEXITY THEORY II: TOWARDS EXPLICIT OBSTRUCTIONS FOR EMBEDDINGS AMONG CLASS VARIETIES. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Mulmuley, Ketan D. – PersonEntity: Name: NameFull: Sohoni, Milind IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 11 Text: 2008 Type: published Y: 2008 Identifiers: – Type: issn-print Value: 00975397 Titles: – TitleFull: SIAM Journal on Computing Type: main |
| ResultId | 1 |
