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
flip hypothesis (fh).
22, 23 The geometric obstruction family is explicit in the
sense that it satisfies the following
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
of a geometric
label based on
theory take triple
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.
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