lower bound problem is reduced to the upper bound problem of constructing a geometric obstruction label in polynomial time.

The following is a stronger and precise explicit form of GOH that says geometric obstructions can indeed be constructed explicitly.

flip hypothesis (fh). 22, 23 The geometric obstruction family is explicit in the sense that it satisfies the following properties:

FH[Short]: A short geometric obstruction label λ, with bit length polynomial in n and m, exists if m is polynomial in n. FH[Verification]: Given n, m, and a partition λ, it can be verified whether λ is a valid geometric obstruction label in time polynomial in n, m and the bit length of λ.

FH[Discovery and construction]: Given n and m, it can be decided whether a geometric obstruction exists in time polynomial in n and m. If an obstruction exists, one such geometric obstruction label λ can also be constructed in the same time. By FH[short], this discovery algorithm always succeeds if m is polynomial in n.

FH[Det]: For given m and λ, it can be verified whether Vλ(G) occurs as a G-subrepresentation in the coordinate ringd of D[det, m] in time polynomial in m and the bit length of λ.

FH[Perm]: For given n, m and λ, it can be verified whether Vλ(G) occurs as a G-subrepresentation in the coordinate ring of D[perm, n, m] in time polynomial in n, m and the bit length of λ.

The flip strategy can now be elaborated further in three steps: ( 1) Prove FH[Det] and FH[Perm]. This clearly implies an efficient criterion for verifying a geometric obstruction label as in FH[Verification]. ( 2) Use this criterion to design an efficient algorithm for discovering an obstruction as in FH[Discovery]. ( 3) Prove that this discovery algorithm always succeeds if m is a polynomial in n. For this strategy to succeed, it is not enough if the verification and discovery algorithms are efficient only in theory. They should also have simple enough mathematical structure to carry out step ( 3). Otherwise, they have to be made simpler and simpler until ( 3) succeeds.

Later, we discuss why FH should d Actually its dual; and similarly in FH[Perm].

The best algorithms
for verification
and construction
of a geometric
obstruction
label based on
general-purpose
algorithms in
algebraic geometry
and representation
theory take triple
exponential time
in n and m in
the worst case.

hold. There is a huge gap between FH and what can be proved at present. Currently, the best algorithms for verification and construction of a geometric obstruction label based on general-purpose algorithms in algebraic geometry and representation theory take triple exponential time in n and m in the worst case. FH says this time bound can be brought down to a polynomial. This may seem impossible.

 

Why Go for explicit Proofs?

If so, one may ask as to why we should go for explicit construction of obstructions when proving existence of obstructions even nonconstructively suffices in principle. The reason is provided by the strong flip theorem. 21 It says that any proof of the arithmetic (strong) permanent vs. determinant conjecture can be converted into an explicit proof assuming a stronger form of a standard derandomization hypothesis12 in complexity theory that is generally regarded as easier than the target lower bound. By an explicit proof, we mean that the proof also yields an algorithm for efficient construction of some proof certificate of hardness of the permanent, called an obstruction, that is analogous to the geometric obstruction above in the following sense: ( 1) its very existence for given n and m guarantees that the inclusion ( 1) is impossible, and ( 2) the family of obstructions satisfies analogues of FH[short], FH[verify], and FH. Thus, by the strong flip theorem, the strong permanent vs. determinant conjecture essentially forces an explicit proof, modulo derandomization.

There are similar flip theorems21 for other lower bound problems, such as the usual permanent vs. determinant and the arithmetic P vs. NP problems, and a certain average case stronger form of the Boolean P vs. NP problem. These results are the main reason why we are going toward explicit proofs, that is, toward explicit construction of obstructions, right from the beginning.

The derandomization hypothesis mentioned here is the following. Its importance is based on the fundamental result in Kabanets and Impagliazzo12 that derandomization means proving circuit lower bounds. Let Y(X) be an m × m matrix, whose each entry is a complex linear combination