Geometric complexity theory: Difference between revisions

Revision as of 22:40, 2 February 2014

Latest revision as of 23:58, 19 June 2025

(15 intermediate revisions by 12 users not shown)

Line 1:

'''Geometric complexity theory (GCT)''', is a research program in [[computational complexity theory]] proposed by [[Ketan Mulmuley]] and Milind Sohoni. The goal of the program is to answer the most famous open problem in computer science – [[P versus NP problem|whether P = NP]] – by showing that the complexity class [[P (complexity) | P]] is not equal to the complexity class [[NP (complexity) | NP]].

The idea behind the approach is to adopt and develop advanced tools in [[algebraic geometry]] and [[representation theory]] (i.e., [[geometric invariant theory]]) to prove lower bounds for problems. Currently the main focus of the program is on [[Arithmetic circuit complexity#Algebraic P and NP | algebraic complexity]] classes. Proving that [[computing the permanent]] cannot be efficiently [[Reduction (complexity)|reduced]] to computing [[determinant]]s is considered to be a major milestone for the program. These computational problems can be characterized by their [[symmetry (mathematics) | symmetries]]. The program aims at utilizing these symmetries for proving lower bounds.

The approach is often considered by some to be the only viable currently active program to separate [[P (complexity) | P]] from [[NP (complexity) | NP]]. However, according to [[Ketan Mulmuley]], believes the program, if viable, is likely to take hundredsabout of100 years before it can settle the [[P vs. NP]] problem.<ref>{{citation

| last = Fortnow | first = Lance

| doi = 10.1145/1562164.1562186

Line 11:

| title = The Status of the P Versus NP Problem

| volume = 52

| year = 2009}}| citeseerx = 10.</ref>1.1.156.767

| s2cid = 5969255

}}.</ref>

The program is pursued by several researchers in mathematics and theoretical computer science. Part of the reason for the interest in the program is the existence of arguments for the program avoiding known barriers such as [[Oracle machine|relativization]] and [[natural proof]]s for proving general lower bounds.<ref>{{Cite journal|last=Mulmuley|first=Ketan D.|date=2011-04-01|title=On P vs. NP and geometric complexity theory: Dedicated to Sri Ramakrishna|url=http://dl.acm.org/citation.cfm?id=1944345.1944346|journal=Journal of the ACM|volume=58|issue=2|pages=5|doi=10.1145/1944345.1944346|s2cid=7703175 |issn=0004-5411|url-access=subscription}}</ref>

==Notes References ==

{{reflist}}

== ReferencesFurther reading ==

K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. SIAM J. Comput. 31(2), 496–526, 2001.

[http://cstheory.stackexchange.com/a/17629 Wikipedia-style explanation of Geometric Complexity Theory] by Joshua Grochow

[GCT1] K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory III: AnTowards ApproachExplicit toObstructions thefor PEmbeddings vs.among NPClass and Related ProblemsVarieties. SIAM J. Comput., 3138(23), 496–5261175–1206, 20012008.

[GCT2] K. D. Mulmuley, H. Narayanan, and M. Sohoni. Geometric Complexitycomplexity Theorytheory IIIII: Towardson Explicitdeciding Obstructionsnonvanishing forof Embeddingsa amongLittlewood-Richardson Class Varietiescoefficient. SIAM J. ComputAlgebraic Combin., 3836 (32012), 1175–1206no. 1, 2008103–110.

[GCT3] K. D. Mulmuley, H. Narayanan, and M. Sohoni. Geometric complexityComplexity theoryTheory IIIV: onEfficient decidingalgorithms nonvanishingfor ofNoether a Littlewood-Richardson coefficientnormalization. J. AlgebraicAmer. CombinMath. 36Soc. 30 (20122017), no. 1, 103–110225-309. [[arxiv:1209.5993|arXiv:1209.5993 [cs.CC]]]

[GCT5] K. D. Mulmuley. Geometric Complexity Theory VVI: Equivalencethe betweenflip blackboxvia derandomizationpositivity., ofTechnical polynomialReport, identityComputer testingScience anddepartment, The derandomizationUniversity of Noether's Normalization Lemma. FOCS 2012Chicago, alsoJanuary arXiv:1209.59932011.

[GCT6] K. D. Mulmuley. Geometric Complexity Theory VI: the flip via positivity., Technical Report, Computer Science department, The University of Chicago, January 2011.

== External links ==

* [http://gct.cs.uchicago.edu/ GCT page, University of Chicago]

* [http://simons.berkeley.edu/workshop_alggeometry1.html Description on the Simons Institute webpage]

* [httphttps://cstheory.stackexchange.com/questions/tagged/gct GCT questions] on [[cstheory]]

* [httphttps://cstheory.stackexchange.com/aq/17629 Wikipedia-style explanation of Geometric Complexity Theory] by Joshua Grochow

* [https://mathoverflow.net/q/277408 What are the current breakthroughs of Geometric Complexity Theory?]

* https://mathoverflow.net/questions/243011/why-should-algebraic-geometers-and-representation-theorists-care-about-geometric/

[[Category:Computational complexity theory]]