Geometric complexity theory: Difference between revisions

Revision as of 21:38, 28 January 2014

Revision as of 22:40, 2 February 2014

Line 3:

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 the only viable currently active program to separate [[P (complexity) | P]] from [[NP (complexity) | NP]]. However, according to [[Ketan Mulmuley]]{{fact|date=January 2014}}, the program is likely to take hundreds of years before it can settle the [[P vs. NP]] problem. <ref>{{citation

| last = Fortnow | first = Lance

| doi = 10.1145/1562164.1562186

| issue = 9

| journal = Communications of the ACM

| pages = 78–86

| title = The Status of the P Versus NP Problem

| volume = 52

| year = 2009}}.</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.

==Notes==

{{reflist}}

== References ==