Exploring the power and potential
of geometric complexity theory.
By ke TAn D. MuLMuLey
the P vs. NP
det( ) sign( ) and
perm( ) ,
i i in
i i in
where xij’s denote the entries of X
and s ranges over all permutations
of the integers from 1 to n. Let K, the
base field or ring of computation, be
Z, Q, C, or a finite field Fp of p
elements, p being an odd prime. We say
that perm(X) can be linearly represented as the determinant of an m × m
matrix if perm(X) = det( Y) for some m
× m matrix Y whose entries are linear
combinations (possibly nonhomogeneous) over K of the variable entries
of X. The permanent vs. determinant
conjecture in Valiant29 is that perm(X)
cannot be linearly represented as the
determinant of an m × m matrix when
m is small, that is, when m is polynomial in n, or more generally, when it is
O(2log an) for some constant a > 0.
It is known3, 29 that this conjecture, when K is Z or Fp, and m is polynomial in n, is implied by a stronger
(nonuniform) versiona of the P ≠ NP
conjecture or even the weaker P
NC conjecture. Here, P denotes the
GeoMetrIC CoMpleXIty theory (GCT) is an approach
via algebraic geometry and representation theory toward
the P vs. NP and related problems.
9, 13, 15, 29 It was proposed
in a series of papers
4, 18–22, 24–26 and was developed further
in bürgisser and Ikenmeyer,
7 bürgisser et al.,
Landsberg et al.
14 This article gives an informal overview
of GCT. Itismeantto be an update on the status
of the P vs. NP problem reported in Fortnow.
Mulmuley23 for a more detailed, formal overview of GCT.
Let us begin by recalling an algebraic variant
of the P vs. NP problem introduced in a seminal
29 It can be formulated in a very concrete form
as the permanent vs. determinant problem. Here the
permanent of an n × n variable matrix X is defined
just like the determinant but without signs.
a This version says that NP contains functions
that cannot be computed by polynomial size
GCT provides an approach to the
foundational questions of complexity
theory via algebraic geometry and
it reveals formidable explicit construction
problems at the crossroads of algebraic
geometry, representation theory, and
complexity theory, and provides evidence
that any approach to the foundational
questions of complexity theory would
have to resolve explicit construction
problems of comparable difficulty.
This law of conservation of difficulty
may explain why P vs. NP and related
problems, which look elementary at the
surface, have turned out to be so difficult.
it shows how to break the circle of self-reference around the arithmetic P vs. NP
and related problems.