Geometric complexity theory: Difference between revisions

Revision as of 22:50, 13 May 2013

Revision as of 12:12, 14 May 2013

Line 1:

Geometric Complexity Theory is a research program in [[computational complexity theory]] proposed by [[Ketan Mulmuly]]. 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]] is not equal to complexity class [[NP]].

Geometric Complexity Theory seeks to address fundamental complexity lower bound questions such as P versus NP by means of algebraic geometry and representation theory.

The basic idea behind the approach is to adopt and develop advanced tools from algebraic geometry and representation theory to prove lower-bounds for problems. Currently the main focus of the program is on algebraic complexity classes. Proving that [[Permanant]] cannot be efficiently reduced to [[Determinant]] is considered to be a major milestone for the program.

The approach is often considered the only currently active serious program to separate P from NP. However, according to Mulmuley the program is likely to take hundreds of years before it can settle the P vs. NP problem. 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 argument for the program avoiding all known [barriers] for proving general lower-bounds.

== External links ==