the strong flip theorem also reveals the
self-referential difficulty in the perma-
nent vs. determinant conjecture.
to see this, let us examine closely
the properties e1–e3 of an explicit proof
that any proof of this conjecture can be
converted into modulo derandomization
by the strong flip theorem. let Sn,m (s) be
a global obstruction set denoted by an
obstruction string s. to verify if Sn,m (s) in-
deed contains a counterexample against
a given point (homogeneous polynomial)
p(Y) OE D[det, m], we have to check if p¢(X)
π perm(X) for some X OE Sn,m(s). assuming
that the permanent is hard to compute,
we cannot check efficiently if p¢(X) π
perm(X) for general X. yet, by e2 (in the
stronger NC-sense), it can be checked
efficiently whether Sn,m(s) contains a
counterexample against every p(Y) OE
DV [g, m] (even in parallel). this seems to
contradict the very hardness of the per-
manent that we are trying to prove.
this self-referential paradox is only
an apparent paradox, because assuming
the permanent vs. determinant conjec-
ture and an additional derandomization
hypothesis we can construct an extremely
explicit proof by the strong flip theorem.
But this is a circular argument. the main
difficulty is to make headway in the
construction of an explicit proof without
making an assumption in any guise that is
as hard as or harder than the target lower
bound assumption.
analogous flip theorems21 reveal simi-
lar self-referential difficulty in other vari-
ants of the P vs. NP problem harder than
derandomization, such as the arithmetic
P vs. NP problem. 25 Intuitively, the appar-
ent self-referential paradox arises because
the P vs. NP conjecture, being a universal
statement about mathematics that says
that discovery is hard, can potentially
make the discovery of its own proof hard.
the situation here is akin to (but far

Self-Referential Difficulty

harder than) the situation for another
universal statement about mathematics,
Gödel’s Incompleteness theorem. this
result says that there are true statements
that cannot be proved. this does not say
that this universal statement itself can-
not be proved. as we know now, it can be
proved. But the crux of this proof is the
resolution of this apparent self-referential
paradox by the construction of a state-
ment that says “I cannot be proved.” simi-
larly, the root difficulty in the P vs. NP (and
the permanent vs. determinant) problem
is the resolution of the apparent self-
referential paradox in the construction
of the statement that says “I am different
from NP (#P).”
In view of this self-referential paradox,
the main conceptual difficulty in proving the
permanent vs. determinant conjecture is to
break the circle of self-reference by decom-
posing the conjecture into subproblems
without the self-referential difficulty.

The Decomposition

We now describe how the circle of self-reference is broken in GCt.

toward this end, observe that fh[det] does not have the self-referential difficulty in the sense that ( 1) m is not required to be a small function of n in its statement, and

( 2) it only depends on the properties of the determinant, and not on the relationship between the permanent and the determinant (or equivalently, between the complexity classes

#P and NC). the case of fh[perm] is similar.

fh[det] and fh[perm] together imply fh[verification], which says that geometric obstructions in Goh are easy to verify. We saw that the self-referential difficulty is the main obstacle to efficient verification of obstructions as needed in e2. hence, once fh[det] and fh[perm] are proved, Goh does not have the self-referential difficulty in verification any more. this decomposes the strong permanent vs. determinant conjecture into three subproblems without the self-referential difficulty in verification, namely, fh[det], fh[perm], and Goh. pictorially,

> ← Strong perm. vs. det.

[][] . FH Det FH Perm GOH + + ( 3)

here the solid arrow ¨ denotes the
formal implication—this follows
trivially since Goh itself implies the
strong permanent vs. determinant
conjecture. the dotted arrow
... > indicates the evidence given in
Mulmuley22 for the plausible converse
based on the strong flip theorem. this
decomposition breaks the circle of self-
reference for verification. Intuitively,
the circle is broken here because
the task of verifying a geometric
obstruction naturally breaks into two
independent tasks, one depending only
on the permanent (i.e., the complexity
class P) and the other only on the
determinant (the complexity class NC).
this is the fundamental difference
between geometric obstructions and
the global obstruction sets in the strong
flip theorem.

is absent in fh[det] and fh[perm]. the
decomposition theorem22, 23 decomposes
the strong permanent vs. determinant
conjecture in terms of these positivity
hypotheses and a more refined form of
Goh (called oh), which too is without
the self-referential difficulty once
the positivity hypotheses are proved.
Unlike ( 3), this decomposition yields
an approach to prove fh[discovery]
in addition to fh[verification]. see
Mulmuley22, 23 for its details.
the positivity hypotheses above
turn out to be formidable because
as explained in Mulmuley22 they
encompass and go much further than
the century-old plethysm problem in
algebraic geometry and representation
theory. since in view of the strong
flip theorem these may be essentially
implications of the strong hardness
and derandomization conjectures,
problems of comparable difficulty
can be expected in any approach. In
this sense, positivity (like explicit
construction) is a hidden root difficulty
underneath the fundamental hardness
conjectures of complexity theory. this
provides yet another reason (in addition
to the strong flip theorem) for why these
conjectures have turned out to be so
hard though they look so elementary at
the surface.
the articles4, 19, 20, 22 suggest an
approach to the positivity hypotheses
via nonstandard quantum groups.
But this story is beyond the scope of
this article.
see Mulmuley22 for the GCt approach
to the arithmetic P vs. NP problem.