Geometric complexity theory: Difference between revisions

Revision as of 12:12, 14 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 MulmulyMulmuley]]. 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]].

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.