(possibly nonhomogeneous) of the variable entries of X. The problem is to decide if det(Y(X) ), for given Y(X), is an identically zero polynomial in the variable entries of X. There is a simple and efficient randomized algorithm for this test. Let A be a matrix obtained from X by substituting for each entry of X a large enough random integer of bit length polynomial in n and m. Evaluate det( Y(A)) modulo a large enough random integer b. If it is nonzero, then det(Y(X)) is certainly a nonzero polynomial. If it is zero, then det(Y(X)) is an identically zero polynomial with a high probability. This randomized test is a black-box test in the sense it only needs to know the value of det(Y(X)) for a given specialization of X to A. It does not need to know Y(X). The derandomization hypothesis mentioned earlier is essentially that this randomized black-box determinant identity test can be efficiently derandomized so as to get an efficiently deterministic black-box determinant identity testing algorithm. (The required hypothesis is actually a bit stronger. 21) This derandomization hypothesis, which is somewhat different from the one in Kabanets and Impagliazzo, 12 is essentially equivalent to proving a determinantal lower bound for a multilinear function that can be evaluated in exponential time1. This is generally regarded as easier than proving a determinantal lower bound for the permanent since P is conjecturally smaller than EXP, the class of functions that can be computed in exponential time.

to state the strong flip theorem, we need a few definitions. let D[det, m], D[perm, n, m],
and V be as in the sidebar “formal definition of the varieties.”
By a global obstruction set for given n and small m polynomial in n, we mean a set
Sn,m = {X1, …, Xl} of nonnegative integral n × n matrices with the following property.
fix any point (homogeneous polynomial) p(Y) OE D[det, m] ⊆ V. let p¢(X) denote the
polynomial obtained from p(Y) by substituting zero for all variables in Y other than z
and X, and 1 for z. then, for any such p(Y ) OE D[det, m], there exists a counterexample
Xi OE Sn, m such that p¢(Xi) π perm(Xi). thus, Sn, m contains a counterexample against
every point in D[det, m] that shows that the point does not specialize to perm(X). this
guarantees that the inclusion as in ( 1) is not possible for given n and m. We say that Sn, m
is small if l is polynomial in n.

We call a proof of the strong permanent vs. determinant conjecture extremely explicit if, for each n and small m polynomial in n, it shows existence of a set of bit strings called obstructions, which serve as proof certificates of hardness of perm(X ), with the following properties e0–e3.

˲ e0 [short]: for every n and small m polynomial in n, there exists a short obstruction of bit length polynomial in n.

˲ e1 [easy to decode]: Given any such short obstruction s for given n and small m polynomial in n, one can construct in time polynomial in n a small global obstruction set Sn,m(s). thus, each short obstruction s denotes a small global obstruction set. ˲ e2 [easy to verify]: Given a bit string s and n and m, it can be decided whether s is the specification of an obstruction for n and m in time polynomial in n and m, and the bit length of s.

˲ e3 [easy to construct]: for each n and small m polynomial in n, a valid obstruction can be constructed in time polynomial in n.

there are some additional technical properties that an extremely explicit proof has to satisfy; see Mulmuley21, 23 for its details. the properties e0, e2, and e3 are analogues of the properties fh[short], fh[verification], and fh[Construction] of geometric obstruction labels (which we identify with geometric obstructions). the geometric obstruction labels also conjecturally satisfy the analogue of e1 for decoding (though this was not stated in the statement of fh).

We call a proof extremely explicit in a stronger N C-sense, if the various algorithms in the conditions e1–e3 work in polylogarithmic time using polynomial number of processors instead of sequential polynomial time.

We say that a technique for proving the strong permanent vs. determinant conjecture is a flip if it leads to an extremely explicit proof of the conjecture. It is called a flip because it reduces the nonexistence problem to the problem of proving existence of obstructions and the lower bound problem to the upper bound problem of finding efficient algorithms to verify, construct, and decode obstructions.

for similar definitions of explicit proofs for other lower bound problems, such as the usual permanent vs. determinant and P vs. NP problems, see Mulmuley. 21, 23

The Strong Flip Theorem

Why should Goh and fh hold? The strong flip theorem21, 23 actually shows something much more. It shows that stronger forms of the permanent vs. determinant and derandomization conjectures together imply an analogue of FH in algebraic geometry of comparable difficulty. This reveals that formidable upper bound problems in algebraic geometry are hidden underneath the fundamental hardness and derandomization conjectures in complexity theory. This may explain why these conjectures, which look so elementary at the surface, have turned out to be so formidable. In view of the strong flip theorem, problems of comparable difficulty can be expected in any approach, even if the approach does not go via algebraic

The Strong Flip Theorem. 21, 23 suppose the strong permanent vs. determinant conjecture holds and that black box determinant identity testing12 can be derandomized (in a stronger form as specified in Mulmuley21). then, the strong permanent vs. determinant conjecture has an extremely explicit proof in the stronger NC-sense. In particular, for any m polynomial in n, an explicit global obstruction set Sn,m can be constructed in time polynomial in n and, more strongly, in polylogarithmic time (in n) using polynomial number of processors.

the proof of the strong flip theorem depends critically on the characterization by symmetries of the permanent as per the property (p). alternatively, one can also use downward self-reducibility of the permanent that has several other applications in complexity theory. 3

Currently, the best algorithms for the construction of a global obstruction set Sn,m based on general purpose algorithms in algebraic geometry take triple exponential time in n and m in the worst case and the bit length of the constructed obstruction is double exponential in the worst case. Bringing this time down to polynomial may seem impossible at the surface. this situation is very similar to that for fh (see the remarks after the statement of fh). thus, the difficulty of proving e0, e1, e2, and e3 for global obstruction sets is comparable to the difficulty of proving fh for geometric obstructions. the strong flip theorem says that the time bound can indeed be brought down to polynomial for geometric obstruction sets assuming the strong permanent vs. determinant conjecture and the derandomization hypothesis.

geometry. We refer to this as the “law of
conservation of difficulty.”
The article by Mulmuley22 gives evi-
dence based on the strong flip theo-
rem and additional results in algebraic
geometry, which suggests that FH itself
may be in essence an implication of the
strong permanent vs. determinant and
derandomization conjectures together.
At present, this is the main evidence for