Communications - June 2012

the cases when K = Z or Q. The advantage of dealing with the arithmetic conjecture over C, in contrast to the original Boolean conjectures, is that this arithmetic conjecture is a statement about multivariate polynomials over C. Hence, we can use techniques from algebraic geometry, which is the study of the common zeroes of sets of multivariate polynomials. These techniques work best when the base field is algebraically closed of characteristic zero, such as C. Since the permanent and the determinant are characterized by their symmetries, we can also use techniques from representation theory, which is the study of groups of symmetries. As such, the GCT approach that goes via algebraic geometry and representation theory is very natural in the arithmetic setting.

The articles by Mulmuley and Sohoni25, 26 reduce the arithmetic permanent vs. determinant conjecture to proving existence of geometric obstructions that are proof certificates of hardness of the permanent. The very existence of these obstructions for given n and m implies that the permanent of an n × n variable matrix cannot be linearly represented as the determinant of an m × m matrix. The geometric obstructions are objects that live in the world of algebraic geometry and representation theory. Their dimensions can be large, exponential in n and m. But they have short classifying labels. The basic strategy of GCT, called the flip, 21, 22 is to construct the classifying label of some geometric obstruction explicitly in time polynomial in n and m when m is small. It is called the flip because it reduces the lower bound problem under consideration to the upper bound problem of constructing a geometric obstruction label efficiently. The flip basically means proving lower bounds using upper bounds. Its basic idea in a nutshell is ( 1) to understand the theory of upper bounds (algorithms) first and ( 2) to use this theory to prove lower bounds later. But one may wonder why we are going for explicit construction of obstructions, when proving existence of an obstruction even nonconstructively suffices in principle. This is because of the flip theorem in Mulmuley, 21, 23 which says that in the problem under consideration we are essentially forced

to construct some proof certificate of hardness explicitly.

The upper bound problems that arise in the context of the flip turn out to be formidable problems at the frontier of algebraic geometry. The flip theorem mentioned above also says that stronger versions of the permanent vs. determinant conjecture and a standard derandomization conjecture12 in complexity theory imply together solutions to the upper bound problems in algebraic geometry that are akin to the ones that arise in the flip. Furthermore the article by Mulmuley22 gives evidence that even the upper bound problems that arise in the flip may be essentially implications of these conjectures in complexity theory. This suggests a law of conservation of difficulty, namely, that problems comparable in difficulty to the ones encountered in GCT would be encountered in any approach to the (nonuniform) P vs. NP problem (of which the arithmetic permanent vs. determinant conjecture over Z is an implication). This does not say that any approach to the P vs. NP problem has to necessarily go via algebraic geometry. But it does suggest that avoiding algebraic geometry may not be pragmatic since it would essentially amount to reinventing in some guise the wheels of this difficult field that have been developed over centuries.

There is also another reason why the explicit construction of geometric obstruction labels turns out to be hard. At the surface it seems that for such efficient construction one may need to compute the permanent itself efficiently, thereby contradicting the very hardness of the permanent that we are trying to prove. By the flip theorem in Mulmuley, 21, 23 this self-referential difficulty akin to that in Gödel’s Incompleteness Theorem is also not specific to GCT. Any approach would have to cope with it. The article by Mulmuley22 shows how it can be tackled in GCT by decomposing the lower bound problem under consideration into subproblems without this difficulty. Conceptually, this is the main result of GCT in the arithmetic setting.

Finally, let us discuss the perma-
nent vs. determinant conjecture over
finite fields that implies the P  NC
conjecture, the story for the algebraic
variant of the P vs. NP problem in
Mulmuley and Sohoni21, 25 that implies
the usual (Boolean) P vs. NP conjecture
being similar. Here, the GCT plan is
to prove the arithmetic case via alge-
braic geometry over C as outlined
above first, and then extend this proof
to finite fields by proving additional
results in algebraic geometry over C,
or rather, algebraically closed fields
of characteristic zero such as C. At the
surface, this plan may seem counter-
intuitive. After all, how can one hope
to prove statements about finite fields
using algebraic geometry over C? A
basic prototype for this plan is the ana-
logue of the usual Riemann hypoth-
esis for finite fields proved in Deligne10
using algebraic geometry over alge-
braically closed fields of characteristic
zero such as C. The proof of this result,
a crowning achievement in mathemat-
ics, shows that difficult statements
about finite fields can be proved using
algebraic geometry over algebraically
closed fields of characteristic zero. In
the same spirit, the GCT approach in
the arithmetic setting can be extended
so that it applies to the usual (Boolean)
#P vs. NC and P vs. NP conjectures. But
this story is beyond the scope of this
article. It will be described in a later
paper. 17 In this article, we confine our-
selves to the arithmetic permanent vs.
determinant problem, which captures
the crux of the P vs. NP problem.

Geometric obstructions

We now describe the GCT approach to the arithmetic permanent vs. determinant problem29 over C based on the notion of geometric obstructions (proof certificates of hardness).