Geometric complexity theory: Difference between revisions

Revision as of 03:25, 6 October 2016

Revision as of 11:34, 4 January 2017

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 considered by some to be the only viable currently active program to separate [[P (complexity) | P]] from [[NP (complexity) | NP]]. However, [[Ketan Mulmuley]] believes the program, if viable, is likely to take about 100 years before it can settle the [[P vs. NP]] problem.<ref>{{citation

| last = Fortnow | first = Lance

| doi = 10.1145/1562164.1562186

Line 18:

{{reflist}}

== Further Readingreading ==

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.