Geometric complexity theory (GCT), is a research program in
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
proposed by
Ketan Mulmuley and Milind Sohoni. The goal of the program is to answer the most famous open problem in computer science –
whether P = NP – by showing that the complexity class
P is not equal to the complexity class
NP.
The idea behind the approach is to adopt and develop advanced tools in
algebraic geometry and
representation theory
Representation theory is a branch of mathematics that studies abstract algebraic structures by ''representing'' their elements as linear transformations of vector spaces, and studies modules over these abstract algebraic structures. In essen ...
(i.e.,
geometric invariant theory
In mathematics, geometric invariant theory (or GIT) is a method for constructing quotients by group actions in algebraic geometry, used to construct moduli spaces. It was developed by David Mumford in 1965, using ideas from the paper in clas ...
) to prove lower bounds for problems. Currently the main focus of the program is on
algebraic complexity
Algebraic may refer to any subject related to algebra in mathematics and related branches like algebraic number theory and algebraic topology. The word algebra itself has several meanings.
Algebraic may also refer to:
* Algebraic data type, a dat ...
classes. Proving that
computing the permanent
In linear algebra, the computation of the permanent of a matrix is a problem that is thought to be more difficult than the computation of the determinant of a matrix despite the apparent similarity of the definitions.
The permanent is defined sim ...
cannot be efficiently
reduced to computing
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if ...
s is considered to be a major milestone for the program. These computational problems can be characterized by their
symmetries
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...
. 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 from
NP. However,
Ketan Mulmuley believes the program, if viable, is likely to take about 100 years before it can settle the
P vs. NP
The P versus NP problem is a major List of unsolved problems in computer science, unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly sol ...
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 existence of arguments for the program avoiding known barriers such as
relativization
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a s ...
and
natural proofs for proving general lower bounds.
References
{{reflist
Further reading
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.
K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties. SIAM J. Comput., 38(3), 1175–1206, 2008.
K. D. Mulmuley, H. Narayanan, and M. Sohoni. Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient. J. Algebraic Combin. 36 (2012), no. 1, 103–110.
K. D. Mulmuley. Geometric Complexity Theory V: Efficient algorithms for Noether normalization. J. Amer. Math. Soc. 30 (2017), no. 1, 225-309.
arXiv:1209.5993 s.CC
K. D. Mulmuley. Geometric Complexity Theory VI: the flip via positivity., Technical Report, Computer Science department, The University of Chicago, January 2011.
External links
GCT page, University of ChicagoGCT questionson
cstheory
Wikipedia-style explanation of Geometric Complexity Theoryby Joshua Grochow
What are the current breakthroughs of Geometric Complexity Theory?
Computational complexity theory