Geometric complexity theory: Difference between revisions

Revision as of 12:37, 14 May 2013

Revision as of 12:38, 14 May 2013

Line 1:

'''Geometric Complexity Theory''', often shortened to '''GCT''', is a research program in [[computational complexity theory]] proposed by [[Ketan Mulmuley]]. The goal of the program is to answer the most famous open problem in computer science [[P vs. NP]] by showing that the complexity class [[P (complexity) | P]] is not equal to the complexity class [[NP (complexity) | NP]].

The basic idea behind the approach is to adopt and develop advanced tools in [[algebraic geometry]] and [[representation 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 [[Permanant]] cannot be efficiently reduced to [[Determinant]] 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 the only currently active serious program to separate [[P (complexity) | P]] from [[NP (complexity) | NP]]. However, according to Mulmuley the program is likely to take hundreds of years before it can settle the [[P vs. NP]] problem.