The Ryan Williams Combine
Structuring his famous proof to build more on it
Ryan Williams is a deep theorist who is known among other things for his frontier-setting lower bounds against circuits. There is also a professional football player named Ryan Williams who played for Virginia Tech in the ACC college conference. The football Ryan had a sub-par showing at the 2011 NFL Combine, which is a series of exercises use by pro scouts to evaluate players, but still became an early second-round pick in the 2011 NFL Draft. Unfortunately he was injured for the entire 2011 NFL season and is out for the rest of this season too. Happily injuries are less of a concern for our Ryan Williams, who married a Virginia.
Today we make a “combine” out of Ryan’s famous lower bound proof. That is, we present it as a series of separate tasks that let us scout opportunities to improve the theorems.
Of course the proof is completely his—this is nothing more than a rearrangement to emphasize different ways that computational problems related to succinctness are employed. We tried to explain the proof two years ago right after it came out, but were not completely successful. Here we will try again with this particular theorem in the paper:
Theorem 1. The complexity class
is not contained in
.
Ryan proves further lower bounds in his paper, but focusing on this one enables us to skirt some technical issues and make the presentation mostly self-contained. We will try to see what properties of are exploited, and what hypotheses are needed, in order to make this apply to a general circuit class
.
Circuit Descriptions
Our framework builds on the notion of circuits that describe a Boolean string. For a circuit with inputs
, let
be the result of evaluating
on the input
. Also we identify strings of length
with the integers
Definition 2. Say that circuit
describes the Boolean string
provided
We will use
to denote this.
The similar capital letter is deliberate.
can be an encoding
of another circuit
, or a computation by a circuit, or an assignment to a Boolean formula on
variables.
We encode general Boolean circuits as directed acyclic graphs using gate types AND, OR, NOT, and INPUT of fan-in at most two. The size of such a circuit is the number of gates. An circuit allows unbounded fan-in gates AND, OR, and MOD
for some fixed
as usual. Its size is the number of wires, and its depth is a constant independent of the number
of input gates.
We allow sizes that are greater than polynomial—indeed we write to mean a quasi-polynomial function, namely one bounded by
for some polynomial
. Note that a circuit of size
needs only
bits to encode. Extra log factors will affect some (sub-)exponential running times, but will not matter to the circuit size bounds. We write
to denote
circuits of size
. Ryan’s paper proves bounds against circuits of size
where
is a higher function; we keep
‘s quasi-polynomial to save on details, but hope the general
notation helps readers who wish to proceed to the stronger results.
Circuit Problems and the Key Property
For a moment think of as any kind of circuit or Turing machine, or even a non-deterministic random-access machine. Given
and a length
, consider these four problems:
-
Evaluate: Given an input
of length
, what is
?
-
Evaluate-all: Evaluate
on all inputs
of length
.
-
Satisfiability: Is there an
of length
such that
?
-
Equivalence: Given circuits
, is there (not) an input
of length
such that
?
If is a circuit of encoding size
, or a machine running in time
, then the notional times to solve these problems deterministically are
for the first, and
for the others. If
(and
) are a non-deterministic machine(s) running in time
, then there exists a small witness for satisfiability, but not necessarily for inequivalence. An important detail is that even if
is a non-deterministic RAM running in time
, there is a non-deterministic TM that simulates it with only
overhead (by “reduction to sorting”). This implies we can get a witness of size
, and also allows us to apply an efficient Cook-Levin construction that works for NTM’s.
The key property of the circuit class is that it can beat the notional time for evaluate-all, in a way that enables even better times for the last two problems. We have talked in general before about new lower bounds flowing from new upper bounds. The general framework is:
-
Prove a better-than-notional upper bound for the target class
on one of the problems.
-
Make a hypothesis
that would amplify the power of
.
- Show this implies a better-than-notional speedup that is actually impossible.
-
Conclude
as a theorem, from which lower bounds follow.
Ryan’s proof translates a tiny savings for satisfiability of circuits into a bigger savings for exponential-time NTMs, one that violates the nondeterministic time hierarchy theorem.
The ACC Algorithms
First we state what is called the “fast evaluation lemma”:
Lemma 3. For any quasi-polynomial
, we can build an algorithm that evaluates a given
-input
-circuit
on all
inputs in time
.
There are three proofs of this now: a matrix based one, a dynamic programming one, and a newer one based on a simple divide and conquer method. For now just take this as true. Now we see how this can be amplified to create a better time for satisfiability and equivalence. We call the following the fast algorithm for
circuits.
Theorem 4. For any
and quasi-polynomial function
, we can build an algorithm that decides whether a given
-input
-circuit
is satisfiable in time
Proof. Select of the inputs of the circuit
. Form all the circuits
by setting the
inputs to all possible values. Then form the new circuit
that is the OR of all these circuits. Clearly
is satisfiable if and only if
is. Further
is a
circuit. Now evaluate
on all the
inputs. By the fast evaluation lemma this takes time
It suffices to make a large enough multiple of
to achieve time
.
Note that there is some slack: we could take to be a polynomial in
, and
would still have quasi-polynomial size. We are abusing notation in whether
means quasi-polynomial in general or a particulat
size, but the usage should be clear in context.
The additional closure properties needed of a circuit class , besides the key speedup, are closure under exclusive-or as used here, closure under composition as used later, and a mix of composition and Boolean operations needed for the “replacement lemma” below. It is not clear whether we need to make the depth
of the composed
circuits explicit in the framework. The particular depth values matter most to quantifying optimal bounds in Ryan’s proof. If the depth needs to be stated up front, at least it applies when trying to prove lower bounds against
in place of
.
The Hypothesis
The key hypothesis we state for sake of contradiction is:
Hypothesis H. The complexity class
has
circuits.
Note this also implies has
circuits, which we call hypothesis H*.
Hypothesis H is stronger than the actual assumption used in Ryan’s paper. The point here is that this simpler assumption will make some of the details less technical, while the ideas and strategy are exactly the same as in the full version. The paper also proves lower bounds against , which is not known to contain
. For this an “easy-witness” property that follows from
is used, but this time we will avoid it.
Having explained why is the target for the lower bound, why do we have
at the upper end? Part of this comes from the following meta-comment about the general approach: In many parts of the proof circuits of type
have to be constructed by an algorithm. In many cases there is no way to deterministically construct the circuits—at least none that are known. The approach used is based on a three-step method:
-
Show via the above assumption that the required circuit
must exist. This only requires that the computation that the circuit performs can be done in the class
.
-
Guess the required circuit
.
-
Then verify that the guessed circuit
is correct. This is exactly where the speedups on equivalence and satisfiability are used.
The special reason for is that the construction builds exponentially large strings that are used as oracle queries to an
oracle. The hypotheses
and
allow us to replace all this by
circuits.
Replacement Lemma
Given a language , let
stand for the
-length bit string of membership results on
. The proof needs only the weaker hypothesis H*, twice.
Lemma 5. Suppose
and let
. Then for any
, we can build a nondeterministic algorithm
that runs in time
, and on input
outputs a
circuit
such that
Proof. By , the algorithm
can generate a uniform sequence
of polynomial-size circuits such that
. The goal is to guess
and verify
, so that
. However, we cannot directly appeal to equivalence testing being in
time because
is not a
circuit but a general circuit.
The trick is to guess a that verifies the computation of
doing evaluate-all on
. This is represented by the language
where we think of . Then
is also in
, so applying hypothesis
here implies the ability to guess a
-circuit
with
inputs (for some fixed
) such that
. The point is that we can verify the correctness of
locally at all gates, including the final output gate
.
To do this verification, we need to represent the encoding of
. We could do this as a single layer of gates computing functions
where
has a
and
where
has a
. However, to illustrate what we can build in
, we instead use
again to guess a
-circuit
with
inputs such that
. In this case
can in fact have polynomial size, and verifying
can be done by brute force evaluation on all possible inputs.
The final circuit stitches together
and
and ultimately outputs
. This evaluate-all task operates within time
since
is a
-circuit. It remains to argue that the verification of the guessed circuit
, in-tandem with the already-verified circuit
, can be reduced to
–
and hence completed in
time. For this we have
build out of
and
yet one more
circuit
with
inputs that works as follows:
On input
, if
are not the inputs to
according to
then reject. If so, make calls
and
to get their values, and compare with the value
. If the values are not correct for the gate
, then accept, else reject.
Then is correct if and only if
is unsatisfiable. Given an exponent
from Theorem 4, this takes time
Taking great enough, as we are able to do, makes the denominator exceed
. Note that
is a Boolean combination of three calls to
and three references to
, so it is a
circuit.
Checking Lemma
The remaining tasks translate an NTM running in time into a succinct formula on
variables, using a known efficient form of the Cook-Levin construction. The following “checking lemma” helps us verify assignments to such formulas.
Lemma 6. Suppose that
and
, where
and
are
circuits with
inputs. Then for any
, there is a deterministic algorithm that runs in time
and checks whether
is a valid assignment to the 3-CNF formula encoded by
.
Proof. We will construct a new circuit
with
inputs. Essentially the circuit “looks for” a clause that is unsatisfied. The circuit
on input
computes the
clause encoded by
. It does this by accessing
consecutive bits of the string
, using
on
consecutive locations to do this. If these bits do not encode a clause, the algorithm rejects. If they do encode a clause, it then finds the three variables
used in the clause and whether they are negated. Then it looks up the values of
by using
three times. Finally if the clause is not satisfied it returns accept; otherwise, it returns reject. It is clear this can be done as a
circuit with
inputs.
The algorithm then must determine whether or not ever accepts. Note
accepts only if
“points” to a proper clause in
that is not satisfied. Similar to the end of the replacement lemma’s proof, it does this by appeal to the fast
–
algorithm.
We note that the checking lemma could be extended to check other “local” properties, but this is enough for the main proof.
Strong Cook-Levin Construction
The following is a known theorem that exploits the locality of the Cook-Levin construction.
Theorem 7. There is a constant
such that for any language
in
there is a deterministic polynomial time algorithm that given input
of length
outputs a circuit
with at most
inputs and size
such that
, where
is a 3-CNF formula of size at most
such that
is in
if and only if
is satisfiable.
With , the proof takes a time-
witness predicate
for
, converts it into circuits
of size
that decide
, and writes a 3-CNF formula
in
variables whose clauses verify that each gate
of
has correct output for its inputs.
Corollary 8. Using the notation of the above theorem, whenever
is a string of length
belonging to
, there exists a
circuit
with at most
inputs such that
, where
is the lexicographically first satisfying assignment to
.
Proof. Construct the formula which is of size at most
. Use the
oracle to find a satisfying assignment, and use it further to do a binary search that finds the lexicographically first one. Since this is done by an
algorithm, Hypothesis
implies the existence of equivalent circuits in
.
To explain a potentially confusing point, note that the proof requires making calls to the oracle on exponentially large strings, since the formula
is exponentially large. This is allowed in
.
Assembling The Proof
Now we combine all these parts into the final theorem and proof.
Proof. Recall we begin by assuming that is contained in
, which entails that
is also in
Now suppose we have a language that is accepted by an NTM running in time
. We will show that it can be accepted by a NTM that runs in time
for some
. This contradiction of the nondeterministic time hierarchy theorem completes the proof.
We break the proof into steps. Let be an input.
(1): Construct a polynomial-size general circuit so that
where
is a 3-CNF formula that is satisfiable if and only if
is in
. Note
is of size
and thus
has
inputs for some
. Note the existence and the ability to create the circuit in polynomial time are based on the Strong Cook-Levin Theorem 7.
(2): Use our replacement lemma 5 to find a circuit
so that
. This circuit has quasi-polynomial size and
inputs—not necessarily the same
as for the circuit
in the proof of that lemma.
(3): Now guess another circuit
with
inputs and quasi-polynomial size so that
where
is satisfying assignment to
. This uses Corollary 8.
(4): Finally accept if is actually such an assignment. This uses the checking lemma 6.
All of this can be done in the required time, and we have a contradiction.
Open Problems
Can we apply the framework to prove lower bounds against other classes ? Does this help us seek for such
? Can we do it with
or even
? Can assuming
help with the latter?
Trackbacks
- Mounting or Solving Open Problems « Gödel’s Lost Letter and P=NP
- NEXP and the Next Generation | Gödel's Lost Letter and P=NP
- DC Post | Gödel's Lost Letter and P=NP
- Alexander Grothendieck 1928–2014 | Gödel's Lost Letter and P=NP
- P=NP: Perhaps I Change My Mind | Gödel's Lost Letter and P=NP
- Cody Murray and Ryan Williams’ new ACC breakthrough: Updates from Oded Goldreich’s Choices | Combinatorics and more
- Progress on the Frontier | Gödel's Lost Letter and P=NP
- Our Thoughts on P=NP | Gödel's Lost Letter and P=NP
Thanks, Pip! I think that this way of partitioning up the proof does shed more light.
I believe that a faster “evaluate-all” algorithm for a circuit class should, in principle, imply stronger lower bounds against that circuit class than just NEXP (e.g., EXP). But a different kind of argument will be required; in the present one, it seems we have to use guessing in order to get our hands on the small witness circuit.
Typo in title: “Wiliams”
Thanks! Now it becomes an experiment to see which links get intelligently forwarded…:-)