Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Geometric complexity theory
open-in-new
<p>Geometric complexity theory (GCT), is a research program in <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> proposed by <a href="/facts/Ketan_Mulmuley/LA9Q4nl8">Ketan Mulmuley</a> and Milind Sohoni. The goal of the program is to answer the most famous open problem in computer science – <a href="/facts/P_versus_NP_problem/xoC7Ruda">whether P = NP</a> – by showing that the complexity class <a href="/facts/P_(complexity)/2TYvck4k">P</a> is not equal to the complexity class <a href="/facts/NP_(complexity)/6muUfVMI">NP</a>. </p><p>The idea behind the approach is to adopt and develop advanced tools in <a href="/facts/Algebraic_geometry/rh7RHVp3">algebraic geometry</a> and <a href="/facts/Representation_theory/3ydLtaGH">representation theory</a> (i.e., <a href="/facts/Geometric_invariant_theory/l4eV0RdG">geometric invariant theory</a>) to prove lower bounds for problems. Currently the main focus of the program is on <a href="/facts/Arithmetic_circuit_complexity/JH8WVCEW">algebraic complexity</a> classes. Proving that <a href="/facts/Computing_the_permanent/uPl6DwHY">computing the permanent</a> cannot be efficiently <a href="/facts/Reduction_(complexity)/IVWF7a1c">reduced</a> to computing <a href="/facts/Determinant/eGYqJ2TF">determinants</a> is considered to be a major milestone for the program. These computational problems can be characterized by their <a href="/facts/Symmetry_(mathematics)/KtLgoqyX">symmetries</a>. The program aims at utilizing these symmetries for proving lower bounds. </p><p>The approach is considered by some to be the only viable currently active program to separate <a href="/facts/P_(complexity)/2TYvck4k">P</a> from <a href="/facts/NP_(complexity)/6muUfVMI">NP</a>. However, <a href="/facts/Ketan_Mulmuley/LA9Q4nl8">Ketan Mulmuley</a> believes the program, if viable, is likely to take about 100 years before it can settle the <a href="/facts/P_vs._NP/xoC7Ruda">P vs. NP</a> problem. </p><p>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 <a href="/facts/Oracle_machine/6ScMuvvY">relativization</a> and <a href="/facts/Natural_proof/CvCNxIg6">natural proofs</a> for proving general lower bounds. </p>