Month: March 2023

Mathematics of the impossible, Chapter 7, Space

As mentioned in Chapter 2, Time is only one of several resources we with to study. Another important one is space, which is another name for the memory of the machine. Computing under space constraints may be less familiar to us than computing under time constraints, and many surprises lay ahead in this chapter that challenge our intuition of efficient computation.

If only space is under consideration, and one is OK with a constant-factor slackness, then TMs and RAMs are equivalent; much like \text {P} is invariant under power changes in time. In a sense, changing the space by a constant factor is like changing the time by a power; from this point of view the equivalence is not surprising.

We shall consider both space bounds bigger than the input length and smaller. For the latter, we have to consider the input separately. The machine should be able to read the input, but not write on its cells. One way to formalize this is to consider 2TMs, where one tape holds the input and is read-only. The other is a standard read-write tape.

We also want to compute functions f whose output is more than 1 bit. One option is to equip the machine with yet another tape, which is write-only. We prefer to stick to two tapes and instead require that given x,i the i output bit of f(x) is computable efficiently.

Definition 7.1. A function f:X\subseteq \{0,1\}^* \to \{0,1\}^* is computable in \text {Space}(s(n)) if there is a 2TM which on input (x,i) on the first tape, where x\in X and i\le |f(x)|, outputs the i bit of f(x), and the machine never writes on the first tape and never uses more than s(|x|) cells on the second.

We define:

\begin{aligned} \text {L}:= & \bigcup _{d}\text {Space}(d\log n),\\ \text {PSpace}:= & \bigcup _{d}\text {Space}(n^{d}). \end{aligned}

We investigate next some basic relationship between space and time.

Theorem 7.1. For every functions t and s:

  1. \text {\ensuremath {k}TM-Time}(t)\subseteq \text {Space}(c_{k}t),
  2. \text {Time}(t)\subseteq \text {Space}(ct\log (nt)),
  3. \text {Space}(s)\subseteq 2\text {TM-Time}(c^{s(n)}\cdot n^{c}).

Proof. 1. A TM running in time t can only move its heads at most t tape cells. We can write all these contents in one tape. To simulate one step of the k\text {TM} we do a pass on all the contents and update them accordingly.

2. A RAM running in time t can only access \le t memory cells, each containing at most c\log nt bits; the factor n is to take into account that the machine starts with word length \ge \log n. We simulate this machine and for each Write operation we add a record on the tape with the memory cell index and the content, similar to Theorem ??. When the RAM reads from memory, we scan the records and read off the memory values from one of them. If the record isn’t found, then the simulation returns the value corresponding to the initial configuration.

We also allocate c\log nt bits for the registers of the RAM. It can be shown that the operations among them can be performed in the desired space, since they only involve a logarithmic number of bits. A stronger result is proved later in Theorem 7.5.

3. On an input x with |x|=n, a \text {Space}(s) machine can be in at most n^{c}\cdot c^{s(n)} configurations. The first n^{c} factor is for the head position on the input. The second factor is for the contents of the second tape. Since the machine ultimately stops, configurations cannot repeat, hence the same machine (with no modification) will stop in the desired time. QED

A non-trivial saving is given by the following theorem.

Theorem 7.2. [12] k\text {-TM-Time}(t)\subseteq \text {Space}(c_{k}t/\log t), for every function t.

This result is not specific to MTMs but can be proved for other models such as RAMs.

From Theorem 7.1 and the next exercise we have

\begin{aligned} \text {L}\subseteq \text {P}\subseteq \text {NP}\subseteq \text {PH}\subseteq \text {PSpace}\subseteq \text {Exp}. \end{aligned}

Exercise 7.1. Prove \text {PH}\subseteq \text {PSpace}.

Just like for Time, for space one has universal machines and a hierarchy theorem. The latter implies \text {L}\ne \text {PSpace}. Hence, analogously to the situation for Time and NTime (section º5.1), we know that at least one of the inclusions above between L and PSpace is strict. Most people seem to think that all are, but nobody can prove that any specific one is.

7.1 Branching programs

Branching programs are the non-uniform counterpart of \text {Space}, just like circuits are the non-uniform counterpart of \text {Time}.

Definition 7.2. A (branching) program is a directed acyclic graph. A node can be labeled with an input variable, in which case it has two outgoing edges labeled 0 and 1. Alternatively a node can be labeled with 0 or 1, in which case it has no outgoing edges. One special node is the start node.

The space of the program with S nodes is \log S. A program computes a function f:\zonzo by following the path from the starting node, following edge labels corresponding to the input, and outputting b\in \{0,1\} as soon as it reaches a node labeled b.

Theorem 7.3. Suppose a 2TM M computes f:\zonzo in space s. Then f has branching programs of space c_{M}(s+\log n). In particular, any f\in \text {L} has branching programs of size n^{c_{f}}.

Proof. Each node in the program corresponds to a configuration. QED

Definition 7.3. The branching program given by Theorem 7.3 is called the configuration graph of M.

The strongest available impossibility result for branching programs is the following.

Theorem 7.4. [16] There are explicit functions (in \text {P}) that require branching programs of size cn^{2}/\log n on inputs of length n.

7.2 The power of L

Computing with severe space bounds, as in L, seems quite difficult. Also, it might be somewhat less familiar than, say, computing within a time bound. It turns out that L is a powerful class capable of amazing computational feats that challenge our intuition of efficient computation. Moreover, these computational feats hinge on deep mathematical techniques of wide applicability. We hinted at this in Chapter 1. We now give further examples. At the same time we develop our intuition of what is computable with little space.

To set the stage, we begin with a composition result. In the previous sections we used several times the simple result that the composition of two maps in P is also in P. This is useful as it allows us to break a complicated algorithm in small steps to be analyzed separately – which is a version of the divide et impera paradigm. A similar composition result holds and is useful for space, but the argument is somewhat less obvious.

Lemma 7.1. Let f_{1}:\{0,1\}^* \to \{0,1\}^* be in \text {Space}(s_{1}) and satisfy |f_{1}(x)|\le m(|x|) for a function m. Suppose f_{2}:\{0,1\}^* \to \{0,1\} is in \text {Space}(s_{2}).

Then the composed function g defined as g(x)=f_{2}(f_{1}(x)) is computable in space c(s_{2}(m(n))+s_{1}(n)+\log nm(n)).

In particular, if f_{1} and f_{2} are in L then g is in L, as long as m\le n^{d} for a constant d.

Exercise 7.2. Prove this.

7.2.1 Arithmetic

A first example of the power of L is given by its ability to perform basic arithmetic. Grade school algorithms use a lot of space, for example they employ space \ge n to multiply two n-bit integers.

Theorem 7.5. The following problems are in L:

  1. Addition of two input integers.
  2. Iterated addition: Addition of any number of input integers.
  3. Multiplication of two input integers.
  4. Iterated multiplication: Multiplication of any number of input integers.
  5. Division of two integers.

Iterated multiplication is of particular interest because it can be used to compute “pseudorandom functions.” Such objects shed light on our ability to prove impossibility results via the “Natural Proofs” connection which we will see in Chapter ??.

Proof of 1. in Theorem 7.5.  We are given as input x,y\in \mathbb {N} and an index i and need to compute bit i of x+y. Starting from the least significant bits, we add the bits of x and y, storing the carry of 1 bit in memory. Output bits are discarded until we reach bit i, which is output. QED

Exercise 7.3. Prove 2. and 3. in Theorem 7.5.

Proving 4. and 5. is more involved and requires some of those deep mathematical tools of wide applicability we alluded to before. Division can be computed once we can compute iterated multiplication. In a nutshell, the idea is to use the expansion

\begin{aligned} \frac {1}{x}=\sum _{i\ge 0}(-1)^{i}(x-1)^{i}. \end{aligned}

We omit details about bounding the error. Instead, we point out that this requires computing powers (x-1)^{i} which is an example of iterated multiplication (and in fact is no easier).

So for the rest of this section we focus on iterated multiplication. Our main tool for this the Chinese-remaindering representation of integers, abbreviated CRR.

Definition 7.4. We denote by \mathbb {Z}_{m} the integers modulo m equipped with addition and multiplication (modulo m).

Theorem 7.6. Let p_{1},...,p_{\ell } be distinct primes and m:=\prod _{i}p_{i}. Then \mathbb {Z}_{m} is isomorphic to \mathbb {Z}_{p_{1}}\times \ldots \times \mathbb {Z}_{p_{\ell }}.

The forward direction of the isomorphism is given by the map

x \in \mathbb {Z}_{m} \rightarrow (x \mod p_{1},x \mod p_{2},...,x \mod p_{\ell }).

For the converse direction, there exist integers e_{1},...,e_{\ell }\leq (p')^{c}, depending only on the p_{i} such that the converse direction is given by the map

(x\mod p_{1},x\mod p_{2},...,x\mod p_{\ell }) \to x:=\sum _{i=1}^{\ell }e_{i}\cdot (x\mod p_{i}).

Each integer e_{i} is 0 mod p_{j} for j\not =i and is 1 mod p_{i}.

Example 7.1. \mathbb {Z}_{6} is isomorphic to \mathbb {Z}_{2}\times \mathbb {Z}_{3}. The equation 2+3=5 corresponds to (0,2)+(1,0)=(1,2). The equation 2\cdot 3=6 corresponds to (0,2)+(1,0)=(0,0). Note how addition and multiplication in CRR are performed in each coordinate separately; how convenient.

To compute iterated multiplication the idea is to move to CRR, perform the multiplications there, and then move back to standard representation. A critical point is that each coordinate in the CRR has a representation of only c\log n bits, which makes it easy to perform iterated multiplication one multiplication at the time, since we can afford to write down intermediate products.

The algorithm is as follows:

Computing the product of input integers x_{1},\ldots ,x_{t}. [6]

  1. Let \ell :=n^{c} and compute the first \ell prime numbers p_{1},p_{2},\ldots ,p_{\ell }.
  2. Convert the input into CRR: Compute (x_{1}\mod p_{1},\ldots ,x_{1}\mod p_{\ell }),\ldots ,(x_{t}\mod p_{1},\ldots ,x_{t}\mod p_{\ell }).
  3. Compute the multiplications in CRR: (\Pi _{i=1}^{t}x_{i}\mod p_{1}),\ldots ,(\Pi _{i=1}^{t}x_{i}\mod p_{\ell }).
  4. Convert back to standard representation.

Exercise 7.4. Prove the correctness of this algorithm.

Now we explain how steps 1, 2, and 3 can be implemented in L. Step 4 can be implemented in L too, but showing this is somewhat technical due to the computation of the numbers e_{i} in Theorem 7.6. However these numbers only depend on the input length, and so we will be able to give a self-contained proof that iterated multiplication has branching programs of size n^{c}.

Step 1

By Theorem ??, the primes p_{i} have magnitude \le n^{c} and so can be represented with c\log n bits. We can enumerate over integers with \le c\log n bits in L. For each integer x we can test if it’s prime by again enumerating over all integers y and z with \le c\log n bits and checking if x=yz, say using the space-efficient algorithm for multiplication in Theorem 7.5. (The space required for this step would in fact be c\log \log n.)

Step 2

We explain how given y\in \{0,1\} ^{n} we can compute (y\mod p_{1},\ldots ,y\mod p_{\ell }) in L. If y_{j} is bit j of y we have that

Step 3

This is a smaller version of the original problem: for each j\leq \ell , we want to compute (\Pi _{i=1}^{t}x_{i}\mod p_{j}) from x_{1}\mod p_{j},\ldots ,x_{t}\mod p_{j}. However, as mentioned earlier, each (x_{i}\mod p_{j}) is at most n^{c} in magnitude and thus has a representation of c\log n bits. Hence we can just perform one multiplication at the time in L.

Step 4

By Theorem 7.6, to convert back to standard representation from CRR we have to compute the map

\begin{aligned} (y\mod p_{1},\ldots ,y\mod p_{\ell })\to \sum _{i=1}^{\ell }e_{i}\cdot (y\mod p_{i}). \end{aligned}

Assuming we can compute the e_{i}, this is just multiplication and iterated addition, which are in L by Theorem 7.5.

Putting the steps together

Combining the steps together we can compute iterated multiplication in L as long as we are given the integers e_{i} in Theorem 7.6.

Theorem 7.7. Given integers x_{1},x_{2},\ldots ,x_{t}, and given the integers e_{1},e_{2},\ldots ,e_{\ell } as in Theorem 7.6, where \ell =n^{c}, we can compute \prod _{i}x_{i} in L.

In particular, because the e_{i} only depend on the input length, but not on the x_{i} they can be hardwired in a branching program.

Corollary 7.1. Iterated multiplication has branching programs of size n^{c}.

Exercise 7.5. Show that given integers x_{1},x_{2},\ldots ,x_{t} and y_{1},y_{2},\ldots ,y_{t} one can decide if

\begin{aligned} \prod _{i=1}^{t}x_{i}=\prod _{i=1}^{t}y_{i} \end{aligned}

in L. You cannot use the fact that iterated multiplication is in L, a result which we stated but not completely proved.

Exercise 7.6. Show that the iterated multiplication of d\times d matrices over the integers has branching programs of size n^{c_{d}}.

7.2.2 Graphs

We now give another example of the power of L.

Definition 7.5. The undirected reachability problem: Given an undirected graph G and two nodes s and t in G determine if there is a path from s to t.

Standard time-efficient algorithms to solve this problem mark nodes in the graph. In logarithmic space we can keep track of a constant number of nodes, but it is not clear how we can avoid repeating old steps forever.

Theorem 7.8. [20] Undirected reachability is in L.

The idea behind this result is that a random walk on the graph will visit every node, and can be computed using small space, since we just need to keep track of the current node. Then, one can derandomize the random walk and obtain a deterministic walk, again computable in L.

7.2.3 Linear algebra

Our final example comes from linear algebra. Familiar methods for solving a linear system

\begin{aligned} Ax=b \end{aligned}

can be done requires a lot of space. For example using elimination we need to rewrite the matrix A. Similarly, we cannot easily compute determinants using small space. However, a different method exists.

Theorem 7.9. [9] Solving a linear system is computable in \text {Space}(c\log ^{2}n).

7.3 Checkpoints

The checkpoint technique is a fundamental tool in the study of space-bounded computation. Let us illustrate it at a high level. Let us consider a graph G, and let us write u\leadsto ^{t}v if there is a path of length \le t from u to v. The technique allows us to trade the length of the path with quantifiers. Specifically, for any parameter b, we can break down paths from u to v in b smaller paths that go through b-1 checkpoints. The length of the smaller paths needs be only t/b (assuming that b divides t). We can guess the breakpoints and verify each smaller path separately, at the price of introducing quantifiers but with the gain that the path length got reduced from t to t/b. The checkpoint technique is thus an instantiation of the general paradigm of guessing computation and verifying it locally, introduced in Chapter 5. One difference is that now we are only going to guess parts of the computation.

The checkpoint technique   u\leadsto ^{t}v\Leftrightarrow \exists p_{1},p_{2},\ldots ,p_{b-1}:\forall i\in \{0,1,b-1\}:p_{i}\leadsto ^{t/b}p_{i+1},   where we denote p_{0}:=u and p_{b}:=v.

An important aspect of this technique is that it can be applied recursively: We can apply it again to the problems p_{i}\leadsto ^{t/b}p_{i+1}. We need to introduce more quantifiers, but we can reduce the path length to t/b^{2}, and so on. We will see several instantiations of this technique, for various settings of parameters, ranging from b=2 to b=n^{c}.

We now utilize the checkpoint technique to show a simulation of small-space computation by small-depth alternating circuits.

Theorem 7.10. A function computable by a branching program with S nodes is also computable by an alternating circuit of depth c\log _{b}S and size S^{b\log _{b}S+c}, for any b\le S.

To illustrate the parameters, suppose S=n^{a}, and let us pick b:=n^{\epsilon } where n\ge c_{a,\epsilon }. Then we have circuits of depth d:=ca/\epsilon and size \le S^{n^{\epsilon }d+c}=2^{n^{c\epsilon }}. In other words, we can have depth d and size 2^{n^{c_{a}/d}}, for every d. This in particular holds for every function in \text {L}. We will later give explicit functions (also in \text {P}) which cannot be computed by circuits of depth d and size 2^{n^{c/d}}, “just short” of ruling out \text {L}. This state of affairs is worth emphasis:

(1) Every f in \text {L} has alternating circuits of depth d and size 2^{n^{c_{f}/d}}. (2) We can prove that there are explicit functions (also in L) which cannot be computed by circuits of depth d and size 2^{n^{c/d}}. (3) Improving the constant in the double exponent for a function in P would yield \text {L}\ne \text {P}. In this sense, the result in (2) is the best possible short of proving a major separation.

Proof. We apply the checkpoint technique to the branching program, recursively, with parameter b. For simplicity we first assume that S is a power of b. Each application of the technique reduces the path length by a factor b. Hence with \log _{b}S applications we can reduce the path length to 1.

In one application, we have an \exists quantifier over b-1 nodes, corresponding to an Or gate with fan-in S^{b-1}, and then a \forall quantifier over b smaller paths, corresponding to an And gate with fan-in b. This gives a tree with S^{b-1}\cdot b\le S^{b} leaves. Iterating, the number of leaves will be

\begin{aligned} (S^{b})^{\log _{b}S}. \end{aligned}

Each leaf can be connected to the input bit on which it depends. The size of the circuit is at most c times the number of leaves.

If S is not a power of b we can view the branching program as having S'\le bS nodes where S' is a power of b . QED

The following is a uniform version of Theorem 7.10, and the proof is similar. It shows that we can speed up space-bounded computation with alternations.

Theorem 7.11. [17]Any f\in L is also in \Sigma _{c_{f}/\epsilon }\text {Time}(n^{\epsilon }), for any \epsilon >0.

Proof. Let G be the configuration graph of f. Note this graph has n^{c_{f}} nodes. We need to decide if the start configuration reaches the accept configuration in this graph within t:=n^{c_{f}} steps.

We apply to this graph the checkpoint technique recursively, with parameter b:=n^{\epsilon /2}. Each application of the technique reduces the path length by a factor b. Hence with c_{f}/\epsilon applications we can reduce the path length to

\begin{aligned} \frac {t}{b^{c_{f}/\epsilon }}=\frac {n^{c_{f}}}{n^{c_{f}/2}}\le 1. \end{aligned}

Each quantifier ranges over b\log n^{c_{f}}=c_{f}n^{\epsilon /2}\log n\le n^{\epsilon } bits for large enough n.

There remains to check a path of length 1, i.e., an edge. The endpoints of this edge are two configurations u and v which depend on the quantified bits. The machine can compute the two endpoints in time \log ^{c}m where m is the total number of quantified bits, using rapid access. Once it has u and v it can check if u leads to v in one step by reading one bit from the input. Note m\le n^{\epsilon }\cdot c_{f}/\epsilon , so \log ^{c}m\le c_{f}n^{\epsilon }. QED

We note that by the generic simulation of alternating time by small-depth circuits in Lemma 6.2, the above theorem also gives a result similar to Theorem 7.10.

7.4 Reductions: L vs. P

Again, we can use reductions to related the space complexity of problems. In particular we can identify the problems in P which have space-efficient algorithms iff every problem in P does.

Definition 7.6. A problem f is P-complete if f\in \text {P} and f\in \text {L}\Rightarrow \text {L}=\text {P}.

Definition 7.7. The circuit value problem: Given a circuit C and an input x, compute C(x).

Theorem 7.12. Circuit value is P-complete.

Proof. Circuit value is in P since we can evaluate one gate at the time. Now let g\in \text {P}. We can reduce computing g on input x to a circuit value instance, as in the simulation of TMs by circuits in Theorem ??. The important point is that this reduction is computable in L. Indeed, given an index to a gate in the circuit, we can compute the type of the gate and index to its children via simple arithmetic, which is in L by Theorem 7.5, and some computation which only depends on the description of the P-time machine for g. QED

Definition 7.8. The monotone circuit value problem: Given a circuit C with no negations and an input x, compute C(x).

Exercise 7.7. Prove that monotone circuit value is P-complete.

Recall from section 7.2.3 that finding solutions to linear systems

\begin{aligned} Ax=b \end{aligned}

has space-efficient algorithms. Interestingly, if we generalize equalities to inequalities the problem becomes P complete. This set of results illustrates a sense in which “linear algebra” is easier than “optimization.”

Definition 7.9. The linear inequalities problem: Given a d\times d matrix A of integers and a d-dimensional vector, determine if the system Ax\le b has a solution over the reals.

Theorem 7.13. Linear inequalities is P-complete.

Proof. The ellipsoid algorithm shows that Linear inequalities is in P, but we will not discuss this classic result.

Instead, we focus on showing how given a circuit C and an input x we can construct a set of inequalities that are satisfiable iff C(x)=1.

We shall have as many variables v_{i} as gates in the circuit, counting input gates as well.

For an input gate g_{i}=x_{i} add equation v_{i}=x_{i}.

For a Not gate g_{i}=\text {Not}(g_{j}) add equation v_{i}=1-v_{j}.

For an And gate g_{i}=\text {And}(g_{j},g_{k}) add equations 0\le v_{i}\le 1,v_{i}\le v_{j},v_{i}\le v_{k},v_{j}+v_{k}-1\le v_{i}.

The case of Or is similar, or can be dispensed by writing an Or using Not and And.

Finally, if g_{i} is the output gate add equation v_{i}=1.

We claim that in every solution to Av\le b the value of v_{i} is the value in \{0,1\} of gate g_{i} on input x. This can be proved by induction. For input and Not gates this is immediate. For an And gate, note that if v_{j}=0 then v_{i}=0 as well because of the equations v_{i}\ge 0 and v_{i}\le v_{j}. The same holds if v_{k}=0. If both v_{j} and v_{k} are 1 then v_{i} is 1 as well because of the equations v_{i}\le 1 and v_{j}+v_{k}-1\le v_{i}. QED

7.4.1 Nondeterministic space

Because of the insight we gained from considering non-deterministic time-bounded computation in section º5.1, we are naturally interested in non-deterministic space-bounded computation. In fact, perhaps we will gain even more insight, because this notion will really challenge our understanding of computation.

For starters, let us define non-deterministic space-bounded computation. A naive approach is to define it using the quantifiers from section º6.4, leading to the class \exists \cdot \text {L}. This is an ill-fated choice:

Exercise 7.8. Prove \exists \cdot \text {L}=\exists \cdot \text {P}.

Instead, non-deterministic space is defined in terms of non-deterministic TMs.

Definition 7.10. A function f:\{0,1\}^* \to \{0,1\} is computable in \text {NSpace}(s(n)) if there is a two-tape TM which on input x never writes on the first tape and never uses more than s(n) cells on the second, and moreover:

1. The machine is equipped with a special “Guess” state. Upon entering this state, a guess bit is written on the work tape under the head.

2. f(x)=1 iff there exists a choice for the guess bits that causes the machine to output 1.

We define

\begin{aligned} \text {NL}:=\bigcup _{d}\text {NSpace}(d\log n). \end{aligned}

How can we exploit this non-determinism? Recall from section 7.2.2 that reachability in undirected graphs is in L. It is unknown if the same holds for directed graphs. However, we can solve it in NL.

Definition 7.11. The directed reachability problem: Given a directed graph G and two nodes s and t, decide if there is a path from s to t.

Theorem 7.14. Directed reachability \text {is in NL}.

Proof. The proof simply amounts to guessing a path in the graph. The algorithm is as follows:

“On input G,s,t, let v:=s.

For i=0 to |G|:

      If v=t, accept.

      Guess a neighbor w of v. Let v:=w.

If you haven’t accepted, reject.”

The space needed is |v|+|i|=c\log |G|. QED

We can define NL completeness similarly to NP and P completeness, and have the following result.

Theorem 7.15. Directed reachability is NL-complete. That is, it is in NL and it is in L iff \text {L}=\text {NL}.

Exercise 7.9. Prove this.

7.4.2 Nspace vs. time

Recall by definition \text {Space}(s(n))\subseteq \text {NSpace}(s(n)). We showed \text {Space}(s(n))\subseteq \text {Time}(n^{c}c^{s(n)}) in Theorem 7.1. We can strengthen the inclusion to show that it holds even for non-deterministic space.

Theorem 7.16. \text {NSpace}(s(n))\subseteq \text {Time}(n^{c}c^{s(n)}).

Proof. On input x, we compute the configuration graph G of M on input x. The nodes are the configurations, and there is an edge from u to v if the machine can go from u to v in one step. Then we solve reachability on this graph in power time, using say breadth-first-search. QED

The next theorem shows that non-deterministic space is not much more powerful than deterministic space: it buys at most a square. Contrast this with the P vs. NP question! The best determistic simulation of NP that we know is the trivial \text {NP}\subseteq \text {Exp}. Thus the situation for space is entirely different.

How can this be possible? The high-level idea, which was used already in Lemma 7.1, can be cast as follows:

Unlike time, space can be reused.

Theorem 7.17. [23] \text {NSpace}(s(n))\subseteq \text {Space}(cs^{2}(n)), for every s(n)\ge \log n. In particular, \text {NPSpace}=\text {PSpace}.

Proof. We use the checkpoint technique with parameter b=2, and re-use the space to verify the smaller paths. Let N be a non-deterministic TM computing a function in \text {NSpace}(s(n)). We aim to construct a deterministic TM M that on input x returns

\begin{aligned} \text {Reach}(C_{\text {start}},C_{\text {accept}},c^{s(n)}), \end{aligned}

where \text {Reach}(u,v,t) decides if v is reachable from u in \le t steps in the configuration graph of N on input x, and C_{\text {start}} is the start configuration, C_{\text {accept}} is the accept configuration, and c^{s(n)} is the number of configurations of N.

The key point is how to implement Reach.

\text {Computing\text { Reach}\ensuremath {(u,v,t)}}

For all “middle” configurations m

\text {If both \text {Reach}\ensuremath {(u,m,t/2)=1} and \text {Reach}\ensuremath {(m,v,t/2)=1} then Accept.}

Reject

Let S(t) denote the space needed for computing \text {Reach}(u,v,t). We have

\begin{aligned} S(t)\le cs(n)+S(t/2). \end{aligned}

This is because we can re-use the space for two calls to Reach. Therefore, the space for \text {Reach}(C_{\text {start}},C_{\text {accept}},c^{s(n)}) is

\begin{aligned} \le cs(n)+cs(n)+\ldots +cs(n)\le cs^{2}(n). \end{aligned}

QED

Recall that we do not know if \text {Ntime}(t) is closed under complement. It is generally believed not to be the case, and we showed that if it is then the PH collapses Exercise 6.3.

What about space? Is \text {NSpace}(s) closed under complement? Theorem 7.17 shows \text {NSpace}(s(n))\subseteq \text {Space}(cs^{2}(n)). So if f\in \text {NSpace}(s(n)) then the complement function 1-f is in \text {Space}(cs^{2}(n)) (and in particular in \text {Space}(cs^{2}(n))). Hence, up to a quadratic loss in space, non-deterministic space is closed under complement.

Can we avoid squaring the space?

Yes! This is weird!

Theorem 7.18. The complement of Path is in NL.

Proof. We want a non-deterministic 2TM that given G,s,\text {and }t accepts if there is no path from s to t in G.

For starters, suppose the machine has computed the number C of nodes reachable from s. The key idea is that there is no path from s to t iff there are C nodes different from t reachable from s. Thus, knowing C we can solve the problem as follows

 

Algorithm for deciding if there is no path from s to t, given C:

  

\text {Initialize \text {Count}=0; Enumerate over all nodes \ensuremath {v\ne t}}

\text {Guess a path from \ensuremath {s} of length \ensuremath {|G|}. If path reaches \ensuremath {v}, increase \text {Count} by \ensuremath {1} }

If \text {Count}=C Accept, else Reject.

 

There remains to compute C.

Let A_{i} be the nodes at distance \le i from s, and let C_{i}:=|A_{i}|. Note A_{0}=\{s\},c_{0}=1. We seek to compute C=C_{n}.

To compute C_{i+1} from C_{i}, enumerate nodes v (candidate in A_{i+1}). For each v, enumerate over all nodes w in A_{i}, and check if w\to v is an edge. If so, increase C_{i+1} by 1.

The enumeration over A_{i} is done guessing C_{i} nodes and paths from s. If we don’t find C_{i} nodes, we reject. QED

7.5 TiSp

So far in this chapter we have focused on bounding the space usage. For this, the TM model was sufficient, as remarked at the beginning. It is natural to consider algorithms that operate in little time and space. For this, of course, whether we use TMs or RAMs makes a difference.

Definition 7.12. Let \text {TiSp}(t,s) be the functions computable on a RAM that on every input x\in \{0,1\} ^{n} runs in time t(n) and only uses memory cells 0 to s(n)-1.

Exercise 7.10. Prove \text {L}=\bigcup _{d}\text {TiSp}(n^{d},d).

An alternative definition of TiSp would allow the RAM to access s(n) cells anywhere in memory. One can maintain a data structure to show that this alternative definition is equivalent to Definition 7.12.

To illustrate the relationship between TiSp, Time, and Space, consider undirected reachability. It is solvable in Time(n\log ^{c}n) by bradth-first search, and in logarithmic space by Theorem 7.8. But it isn’t known if it is in \text {TiSp}(n\log ^{a}n,a\log n) for some constant a.

Exercise 7.11. Prove that Theorem 7.11 holds even for any function f in \text {TiSp}(n^{a},n^{1-\epsilon }) for any a and \epsilon >0.

The following is a non-uniform version of TiSp.

Definition 7.13. A branching program of length t and width W is a branching program where the nodes are partitioned in t layers L_{1},L_{2},\ldots ,L_{t} where nodes in L_{i} only lead to nodes in L_{i+1}, and |L_{i}|\le W for every i.

Thus t represents the time of the computation, and \log W the space.

Recall that Theorem 7.10 gives bounds of the form \ge cn^{2}/\log n on the size of branching program (without distinguishing between length and width). For branching programd og length t and width W this bound gives t\ge cn^{2}/W\log n. But it gives nothing for power width like W=n^{2}. The state-of-the-art for power width is t\ge \Omega (n\sqrt {\log n/\log \log n}) [2, 7] (in fact the bound holds even for subexponential) .

With these definitions in hand we can refine the connection between branching programs and small-depth circuits in Theorem 7.10 for circuits of depth 3.

Theorem 7.19. Let f:\{0,1\} ^{n}\to \{0,1\} be computable by a branching program with width W and time t. Then f is computable by an alternating depth-3 circuit with \le 2^{c\sqrt {t\log W}} wires.

We will later show explicit functions that require depth-3 circuits of size 2^{c\sqrt {n}}. Theorem 7.19 shows that improving this would also improve results for small-width branching programs, a refinement of the message emphasized before after Theorem 7.10.

Exercise 7.12. Prove this.

7.6 Notes

For a discussion of the complexity of division, see [3]. For a compendium of P-complete problems see [11].

References

[1]   Mikl≤s Ajtai. \Sigma \sp {1}\sb {1}-formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1–48, 1983.

[2]   Mikl≤s Ajtai. A non-linear time lower bound for boolean branching programs. Theory of Computing, 1(1):149–176, 2005.

[3]   Eric Allender. The division breakthroughs. Bulletin of the EATCS, 74:61–77, 2001.

[4]   Noga Alon, Oded Goldreich, Johan Hσstad, and RenΘ Peralta. Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992.

[5]   Kenneth E. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Computing Conference, volume 32, pages 307–314, 1968.

[6]   Paul Beame, Stephen A. Cook, and H. James Hoover. Log depth circuits for division and related problems. SIAM J. Comput., 15(4):994–1003, 1986.

[7]   Paul Beame, Michael Saks, Xiaodong Sun, and Erik Vee. Time-space trade-off lower bounds for randomized computation of decision problems. J. of the ACM, 50(2):154–195, 2003.

[8]   Stephen A. Cook. A hierarchy for nondeterministic time complexity. J. of Computer and System Sciences, 7(4):343–353, 1973.

[9]   L. Csanky. Fast parallel matrix inversion algorithms. SIAM J. Comput., 5(4):618–623, 1976.

[10]   Aviezri S. Fraenkel and David Lichtenstein. Computing a perfect strategy for n x n chess requires time exponential in n. J. Comb. Theory, Ser. A, 31(2):199–214, 1981.

[11]   Raymond Greenlaw, H. James Hoover, and Walter Ruzzo. Limits to Parallel Computation: P-Completeness Theory. 02 2001.

[12]   John E. Hopcroft, Wolfgang J. Paul, and Leslie G. Valiant. On time versus space. J. ACM, 24(2):332–337, 1977.

[13]   Richard M. Karp and Richard J. Lipton. Turing machines that take advice. L’Enseignement MathΘmatique. Revue Internationale. IIe SΘrie, 28(3-4):191–209, 1982.

[14]   Leonid A. Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):115–116, 1973.

[15]   Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. on Computing, 22(4):838–856, 1993.

[16]   E. I. Nechiporuk. A boolean function. Soviet Mathematics-Doklady, 169(4):765–766, 1966.

[17]   Valery A. Nepomnjaščiĭ. Rudimentary predicates and Turing calculations. Soviet Mathematics-Doklady, 11(6):1462–1465, 1970.

[18]   NEU. From RAM to SAT. Available at http://www.ccs.neu.edu/home/viola/, 2012.

[19]   Wolfgang J. Paul, Nicholas Pippenger, Endre SzemerΘdi, and William T. Trotter. On determinism versus non-determinism and related problems (preliminary version). In IEEE Symp. on Foundations of Computer Science (FOCS), pages 429–438, 1983.

[20]   Omer Reingold. Undirected connectivity in log-space. J. of the ACM, 55(4), 2008.

[21]   J. M. Robson. N by N checkers is exptime complete. SIAM J. Comput., 13(2):252–267, 1984.

[22]   Rahul Santhanam. On separators, segregators and time versus space. In IEEE Conf. on Computational Complexity (CCC), pages 286–294, 2001.

[23]   Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177–192, 1970.

[24]   Michael Sipser. A complexity theoretic approach to randomness. In ACM Symp. on the Theory of Computing (STOC), pages 330–335, 1983.

[25]   Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. on Computing, 20(5):865–877, 1991.

[26]   Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theor. Comput. Sci., 47(3):85–93, 1986.

[27]   N. V. Vinodchandran. A note on the circuit complexity of PP. Theor. Comput. Sci., 347(1-2):415–418, 2005.

[28]   Emanuele Viola. On approximate majority and probabilistic time. Computational Complexity, 18(3):337–375, 2009.

Mathematics of the impossible: Computational Complexity, Chapter 6, Alternation

We placed one quantifier “in front” of computation and got something interesting: NP. So let’s push the envelope.

Definition 6.1. \Sigma _{i}Time(t(n)) is the set of functions f:X\subseteq \{0,1\}^* \to \{0,1\} for which there is a RAM M such that on input (x,y_{1},y_{2},\ldots ,y_{i}) stops within t(|x|) steps and

\begin{aligned} f(x)=1\Leftrightarrow \exists y_{1}\forall y_{2}\exists y_{3}\forall y_{4}\ldots Q_{i}y_{i}\in \{0,1\} ^{t(|x|)}:M(x,y_{1},y_{2},\ldots ,y_{i})=1. \end{aligned}

\Pi _{i}Time(t(n)) is defined similarly except that we start with a \forall quantifier. We also define

\begin{aligned} \text {\ensuremath {\Sigma _{i}\text {P}}}:= & \bigcup _{d}\Sigma _{i}\text {Time}(n^{d}),\\ \text {\ensuremath {\Pi _{i}\text {P}}}:= & \bigcup _{d}\Pi _{i}\text {Time}(n^{d}),\text { and}\\ \text {the power hiearchy PH}:= & \bigcup _{i}\Sigma _{i}\text {P}=\bigcup _{i}\Pi _{i}\text {P}. \end{aligned}

We refer to such computation and the corresponding machines as alternating, since they involve alternation of quantifiers and we will soon see a connection with alternating circuits.

As for NP, Definition 5.1, note that the running time of M is a function of |x| only. Again, this difference is inconsequential for \Sigma _{i}\text {P}, since the composition of two powers is another power. But it is important for a more fine-grained analysis.

Exercise 6.1. Min-Ckt is the problem of deciding if an input circuit has an equivalent circuit which is smaller. It is not known to be in NP. In which of the above classes can you place it?

6.1 Does the PH collapse?

We refer to the event that \exists i:\Sigma _{i}\text {P}=\text {PH} as “the PH collapses.” It is unknown if the PH collapses. Most people appear to believe that it does not, and to consider statements of the type

\begin{aligned} X\Rightarrow \text {PH collapses} \end{aligned}

as evidence that X is false. Examples of such statements are discussed next.

Theorem 6.1. \text {P}=\text {NP}\Rightarrow \text {P}=\text {PH}.

The idea in the proof is simply that if you can remove a quantifier then you can remove more.

Proof. We prove by induction on i that \Sigma _{i}\text {P}\bigcup \Pi _{i}\text {P}=\text {P}.

The base case i=1 follows by assumption and the fact that P is closed under complement.

Next we do the induction step. We assume the conclusion is true for i and prove it for i+1. We will show \Sigma _{i+1}\text {P}=\text {P}. The result about \Pi _{i+1}P follows again by complementing.

Let L\in \sum _{i+1}\text {P}, so \exists a and a power-time TM M such that for any x\in \{0,1\} ^{n},

\begin{aligned} x\in L\Leftrightarrow \exists y_{1}\forall y_{2}\exists y_{3}\forall y_{4}\ldots Q_{i+1}y_{i+1}\in \{0,1\} ^{n^{a}}:M(x,y_{1},y_{2},\ldots ,y_{i+1})=1. \end{aligned}

(As discussed after Definition 6.1 we don’t need to distinguish between time as a function of |x| or of |(x,y_{1},y_{2},\text {\dots },y_{i+1})| when considering power times as we are doing now.)

Now the creative step of the proof is to consider

\begin{aligned} L':=\left \{ (x,y_{1}):\forall y_{2}\in \{0,1\} ^{n^{a}}\ldots Q_{i+1}y_{i+1}\in \{0,1\} ^{n^{a}}:M(x,y_{1},y_{2},\ldots ,y_{i+1})=1\right \} . \end{aligned}

Note L'\in \Pi _{i}\text {P}. By induction hypothesis L'\in \text {P}. So let TM M' solve L' in power time. So x\in L\iff \exists y_{1}\in \{0,1\} ^{n^{a}}:M'(x,y_{1})=1. And so L\in \text {NP\ensuremath {=\text {P}}}, again using the hypothesis. QED

Exercise 6.2. Prove the following strengthening of Theorem 6.1:

\begin{aligned} \bigcup _{d}\text {NTime}(dn)\subseteq \text {Time}(n^{1+\epsilon })\Rightarrow \bigcup _{d}\text {\ensuremath {\Sigma _{i}\text {Time}(dn)\subseteq \text {Time}(n^{1+\epsilon ^{c_{i}}})}.} \end{aligned}

Exercise 6.3. Show that if \Sigma _{i}\text {P}=\Pi _{i}\text {P} for some i then the PH collapses to \Sigma _{i}\text {P}, that is, \text {PH}=\Sigma _{i}\text {P}.

Theorem 6.2. [21] \text {NP}\subseteq \text {PCkt}\Rightarrow \text {PH}=\Sigma _{2}\text {P}.

Proof. We’ll show \Pi _{2}\text {P}\subseteq \Sigma _{2}\text {P} and then appeal to Exercise 6.3. Let f\in \Pi _{2}\text {Time}(n^{d}) and M be a corresponding machine s.t. 

\begin{aligned} f(x)=1\Leftrightarrow \forall y_{1}\in \{0,1\} ^{n^{d}}\exists y_{2}\in \{0,1\} ^{n^{d}}:M(x,y_{1},y_{2})=1. \end{aligned}

We claim the following equivalent expression for the right-hand side above:

\begin{aligned} \forall y_{1}\in \{0,1\} ^{n^{d}}\exists y_{2}\in \{0,1\} ^{n^{d}}:M(x,y_{1},y_{2})=1\Leftrightarrow \exists C\forall y_{1}\in \{0,1\} ^{n^{d}}:M(x,y_{1},C(x,y_{1}))=1, \end{aligned}

where C ranges over circuits of size |x|^{d'} for some d'. If the equivalence is established the result follows, since evaluating a circuit can be done in power time.

To prove the equivalence, first note that the the \Leftarrow direction is obvious, by setting y_{2}:=C(x,y_{1}). The interesting direction is the \Rightarrow . We claim that under the assumption, there is a circuit that given x,y_{1} outputs a string y_{2} that makes M(x,y_{1},y_{2}) accept, if there is such a string.

To verify this, consider the problems CktSat and Search-CktSat which are analogous to the 3Sat and Search-3Sat problems but for general circuits rather than 3CNF. CktSat is in NP, and so by assumption has power-size circuits. By the reduction in Theorem 4.5, Search-CktSat has power-size circuits S as well. Hence, the desired circuit C may, on input x and y_{1} produce a new circuit W mapping an input y_{2} to M(x,y_{1},y_{2}), and run S on W. QED

Exercise 6.4. Prove that \text {PH}\not \subseteq \text {CktGates}(n^{k}), for any k\in \mathbb {N}. (Hint: Existentially guess the truth table of a hard function.)

Improve this to \text {\ensuremath {\Sigma _{2}\text {P}}}\not \subseteq \text {CktGates}(n^{k}).

Exercise 6.5. Prove \text {Exp}\subseteq \text {PCkt}\Rightarrow \text {Exp}=\Sigma _{2}\text {P}.

6.2 PH vs. alternating circuits

As suggested by the word alternation in Definition 6.1, the power hierarchy PH and its subclasses can be seen as alternating circuits. Before presenting this connection it is useful to write problems in PH in a specific format. The next lemma shows that we can restrict the machine M in Definition 6.1 to read only one bit of the input x. The price for this is that we are going to have to introduce an extra quantifier, however this new quantifier will only range over \log t bits.

Lemma 6.1. Let L\in \Sigma _{i}\text {P}. Then there exists a RAM M s.t.:

\begin{aligned} x\in L\Leftrightarrow & \exists y_{1}\in \{0,1\} ^{t(|x|)}\forall y_{2}\in \{0,1\} ^{t(|x|)}\ldots Q_{i-1}y_{i-1}\in \{0,1\} ^{t(|x|)}\\ & Q_{i}(y_{i},z)\in \{0,1\} ^{2t(|x|)}Q_{i+1}y_{i+1}\in \{0,1\} ^{\log t(|x|)}:M(x,y_{1},y_{2},\ldots ,y_{i+1})=1, \end{aligned}

and M on input (x,y_{1},y_{2},\ldots ,y_{i+1}) stops within ct(|x|) steps and only reads one bit of x.

Note the first i-1 quantifiers are over t bits and unchanged from Definition 6.1, the next one is over 2t bits, written as a pair (y_{i},z), and the last is over \log t. The idea is… you guessed it! We are going to guess the bits read from the input, and verify that each of them is correct.

Proof. Let M' be the machine corresponding to L in Definition 6.1. We assume that Q_{i}=\exists , i.e., i is odd. The case Q_{i}=\forall is left for exercise.

We enlarge Q_{i} to quantify over additional t bits z which correspond to the bits of x read by M'. The desired machine M simulates M' with the following change. At any time step s, if M' reads bit j of x:

(1) If s\ne y_{i+1} then M does not read x and instead uses bit z_{s},

(2) If s=y_{i+1} then M reads the corresponding bit of x, and it also checks that this bit equals z_{s}. If it doesn’t M rejects.

By inspection, M reads at most one bit of x.

Correctness is argued as follows. For any y_{1},y_{2},\ldots ,y_{i}, if M' accepts x then there are values z for the bits read from the input x that cause M to accept. Conversely, if M accepts for some z then this z matches the bits read from x by M', for else M would reject in (2). Hence M' accepts x as well. QED

We now show how to simulate computation in PH by small-depth circuits. The size of the circuit is exponential in the time; such a simulation would not be interesting if the circuit is not explicit and the time is more than the input length, since every function on n bits has circuits of size 2^{n} (Theorem 2.3). By contrast, the simulation will give explicit circuits and also apply to running times less than the input length. The setting of running time less than the input length makes the simulation interesting even for non-explicit circuits, and is soon to play a critical role.

Lemma 6.2. Any function in \Sigma _{d}\text {Time}(t)\bigcup \Pi _{d}\text {Time}(t) has on inputs of length n alternating circuits of depth d+1 and 2^{cdt(n)} gates. The fan-in of each gate is \le 2^{ct(n)} and the fan-in of the gates closest to the input is \le t(n). Moreover, the circuit is explicit in the following sense: Given an index to a gate g of fan-in h and a number i\le h we can compute the index of child i of g in \text {Time}(cn).

In fact, most of this circuit only depends on t. The only thing that depends on the actual function being computed are the connections between the gates closest to the input and the input.

Proof. We apply Lemma 6.1. Then an \exists (resp. \forall ) quantifier on b bits corresponds to an Or (resp. And) gate with fan-in 2^{b}. A gate g closest to the input correspond to the computation of the RAM for fixed quantified variables. This computation depends on at most one bit of x. If this computation is a constant independent of x, we simply replace this gate with the appropriate constant. Otherwise, if it depends on a bit x_{j} of x then the computation of the RAM is either x_{j} or \neg x_{j}. Thus we can connect gate g to either input gate x_{j} or input gate \neg x_{j}.

An index to a gate g next to the input is just an assignment to the quantified variables y_{i}. Given such an index and i\le t we can compute in linear time which input bit it depends on. This is done by simulating the machine until the i-th time it reads an input bit. Note this simulation runs in time ct which is linear in the length of an index to the gate. QED

6.3 BPP in PH

It is not known if BPP is contained in NP. However, we can show that BPP is in PH. More precisely, the following two simulations are known. The first optimizes the number of quantifiers, the second the time. This should be contrasted with various conditional results suggesting that in fact a quasilinear deterministic simulation (with no quantifiers) is possible.

Theorem 6.3. For every function t we have:

(1) [35] \text {BPTime}(t)\subseteq \Sigma _{2}\text {Time}(t^{2}\log ^{c}t), and

(2) [4
1] \text {BPTime}(t)\subseteq \Sigma _{3}\text {Time}(t\log ^{c}t).

A good way to think of these results is as follows. Fix a \text {BPTime}(t) machine M and an input x\in \{0,1\} ^{n}. Now the alternating machine is trying to decide if for most choices of the random bits y we have M(x,y)=1, or if for most choices we have M(x,y)=0. This can be seen as a version of the Majority problem, with two critical features. The first is that it is succinct in the sense of section 5.4.1, that is, the alternating machine does not have access to the exponentially-long majority instance, but rather has access to a small circuit M(x,\cdot ) s.t. M(x,y) is bit y of the majority instance. The second is that instances have a gap. We define this gap-majority problem next. We define the non-succinct version which is of independent interest, and so use the letter n to indicate input length. But recall that for the application later in this section the input is given succinctly, as just remarked, so the gap majority instance will actually be on a number of bits that is exponential in the input length to the alternating machine.

Definition 6.2. \text {Gap-Maj}_{\alpha ,\beta } is the problem of deciding if an input x\in \{0,1\} ^{n} has weight |x|\le \alpha n or |x|\ge \beta n.

As discussed in section º6.2, it is useful to think of alternating computation as alternating circuits. Indeed, the circuit result that is the starting point of all these simulations is the following somewhat surprising construction of small-depth alternating circuits for Gap-Maj. By contrast, (non-gap) Maj does not have small constant-depth alternating circuits, as we will prove in Chapter ??.

Lemma 6.3. [3]\text { Gap-Maj}_{1/3,2/3}(x) has alternating circuits of depth 3 and size n^{c}. Moreover, the gates at distance 1 from the input have fan-in \le c\log n.

Proof. This is a striking application of the probabilistic method. For a fixed pair of inputs (x,y) we say that a distribution C on circuits gives (\le p,\ge q) if \mathbb {P}_{C}[C(x)=1]\le p and \mathbb {P}_{C}[C(y)=1]\ge q; and we similarly define gives with reverse inequalities. Our goal is to have a distribution that gives

\begin{aligned} (\le 2^{-n},\ge 1-2^{-n})~~~~(6.1) \end{aligned}

for every pair (x,y)\in \{0,1\} ^{n}\times \{0,1\} ^{n} where |x|\le n/3 and |y|\ge 2n/3. Indeed, if we have that we can apply a union bound over the <2^{n} inputs to obtain a fixed circuit that solves Gap-Maj.

We construct the distribution C incrementally. Fix any pair (x,y) as above. Begin with the distribution C_{\wedge } obtained by picking 2\log n bits uniformly from the input and computing their And. This gives

\begin{aligned} \left ((1/3)^{2\log n},(2/3)^{2\log n}\right ). \end{aligned}

Let p:=(1/3)^{2\log n} and note (2/3)^{2\log n}=p\cdot n^{2}. So we can say that C_{\wedge } gives

\begin{aligned} \left (\le p,\ge p\cdot n^{2}\right ). \end{aligned}

Now consider the distribution C_{\vee } obtained by complementing the circuits in C_{\wedge }. This gives

\begin{aligned} \left (\ge 1-p,\le 1-p\cdot n^{2}\right ). \end{aligned}

Next consider the distribution C_{\wedge \vee } obtained by taking the And of m:=p^{-1}/n independent samples of C_{\vee }. This gives

\begin{aligned} \left (\ge (1-p)^{m},\le (1-p\cdot n^{2})^{m}\right ). \end{aligned}

To make sense of these quantities we use the basic approximations

\begin{aligned} 1+z \le e^{z }\le 1+2z \end{aligned}

valid for all z \in [0,1]. These imply (1-p)^{m}\ge e^{-pm/2}=e^{-1/(2n)}\ge 0.9 and (1-p\cdot n^{2})^{m}\le e^{-n}. Summarizing, this gives

\begin{aligned} (\ge 0.9,\le e^{-n}). \end{aligned}

Next consider the distribution C_{\vee \wedge } obtained by complementing the circuits in C_{\wedge \vee }. This gives

\begin{aligned} (\le 0.1,\ge 1-e^{-n}). \end{aligned}

Finally, consider the distribution C_{\wedge \vee \wedge } obtained by taking the And of n independent samples of C_{\vee \wedge }. This gives

\begin{aligned} \left (\le 0.1^{n},\ge \left (1-e^{-n}\right )^{n}\right ). \end{aligned}

To make sense of the rightmost quantity we can use the approximation

\begin{aligned} (1+\alpha )^{r}\ge 1+r\alpha \end{aligned}

valid for all \alpha \ge -1 and r\ge 1. Thus this gives

\begin{aligned} \left (\le 0.1^{n},\ge 1-ne^{-n}\right ). \end{aligned}

We have ne^{-n}<2^{-n}. Thus this distribution in particular gives equation (??). The bounds on the number of gates and the fan-in holds by inspection. QED

Exercise 6.6. Prove \text { Gap-Maj}_{1/2-1/\sqrt {\log n},1/2+1/\sqrt {\log n}} has alternating circuits of depth c and size n^{c}.

Exercise 6.7. Assume the circuit in Lemma 6.3 is explicit in the sense of Lemma 6.2. Prove Theorem 6.3.

There remains to construct explicit circuits for Gap-Maj. We give a construction which has worse parameters than Lemma 6.3 but is simple and suffices for (1) in Theorem 6.3. The idea is that if the input weight of x is large, then we can find a few shifts of the ones in x that cover each of the n bits. But if the weight of x is small we can’t. By “shift” by s we mean the string x_{i\oplus s}, obtained from x by permuting the indices by xoring them with s. (Other permutations would work just as well.)

Lemma 6.4. Let r:=\log n. The following circuit solves \text {GapMaj}_{1/r^{2},1-1/r^{2}} on every x\in \{0,1\} ^{n}:

\begin{aligned} \bigvee s_{1},s_{2},\ldots ,s_{r}\in \{0,1\} ^{r}:\bigwedge i\in \{0,1\} ^{r}:\bigvee j\in \{1,2,\ldots ,r\}:x_{i\oplus s_{j}}. \end{aligned}

Note that

\begin{aligned} \bigwedge i\in \{0,1\} ^{r}:\bigvee j\in \{1,2,\ldots ,r\}:x_{i\oplus s_{j}} \end{aligned}

means that every bit i is covered by some shift s_{j} of the input x.

Proof. Assume |x|\le n/r^{2}. Each shift s_{i} contributes at most n/r^{2} ones. Hence all the r shifts contribute \le n/r ones, and we do not cover every bit i.

Now assume |x|\ge n(1-1/r^{2}). We show the existence of shifts s_{i} that cover every bit by the probabilistic method. Specifically, for a fixed x we pick the shifts uniformly at random and aim to show that the probability that we do not cover every bit is <1. Indeed:

\begin{aligned} \begin{aligned} & \mathbb {P}_{s_{1},s_{2},\ldots ,s_{r}}[\exists i\in \{0,1\} ^{r}:\forall j\in \{1,2,\ldots ,r\}:x_{i\oplus s_{j}}=0]\\ \le & \sum _{i\in \{0,1\} ^{r}}\mathbb {P}_{s_{1},s_{2},\ldots ,s_{r}}[\forall j\in \{1,2,\ldots ,r\}:x_{i\oplus s_{j}}=0] & \text {(union bound)}\\ = & \sum _{i\in \{0,1\} ^{r}}\mathbb {P}_{s}[x_{i\oplus s}=0]^{r} & \text {(independence of the }s_{i}\text {)}\\ \le & \sum _{i\in \{0,1\} ^{r}}(1/r^{2})^{r} & \text {(by assumption on }|x|\text {)}\\ \le & (2/r^{2})^{r}\\ < & 1, \end{aligned} \end{aligned}

as desired. QED

Exercise 6.8. Prove (1) in Theorem 6.3.

Lemma 6.4 is not sufficient for (2) in Theorem 6.3. One can prove (2) by derandomizing the shifts in Lemma 6.4. This means generating their r^{2} bits using a seed of only r\log ^{c}r bits (instead of the trivial r^{2} in Lemma 6.4.).

Exercise 6.9. Prove:

(1) \text {P}=\text {NP}\Rightarrow \text {P}=\text {BPP}.

(2) \Sigma _{2}\text {P}\subseteq \text {BPP}\Rightarrow \text {PH collapses}.

6.4 The quantifier calculus

We have extended \text {P} with \exists and \forall quantifiers. We have also extended it with randomness to obtain \text {BPP}. As alluded to before, we can also think of BPP as a quantifier \text {BP} applied to \text {P}. The Unique-3Sat problem (Theorem 5.8) also points to a new quantifier, “exists unique.” We now develop a general calculus of quantifiers, and examine fundamental relationships between then. For simplicity, we only consider power-time computation.

Definition 6.3. Let C be a class of functions mapping \{0,1\}^* \to \{0,1\} . We define L\in \text {Op}\cdot C if there is L'\in C and d\in \mathbb {N} such that

  • \text {Op}=\text {Maj}
    \begin{aligned} x\in L & \Leftrightarrow \mathbb {P}_{y\in \{0,1\} ^{|x|^{d}}}[(x,y)\in L']\ge 1/2. \end{aligned}
  • \text {Op}=\text {BP}
    \begin{aligned} x\in L & \Rightarrow \mathbb {P}_{y\in \{0,1\} ^{|x|^{d}}}[(x,y)\in L']\ge 2/3,\\ x\not \in L & \Rightarrow \mathbb {P}_{y\in \{0,1\} ^{|x|^{d}}}[(x,y)\in L']\le 1/3. \end{aligned}
  • \text {Op}=\oplus (read: parity)
    \begin{aligned} x\in L\Leftrightarrow \text {there is an odd number of }y\in \{0,1\} ^{|x|^{d}}:(x,y)\in L'. \end{aligned}
  • \text {Op}=\exists
    \begin{aligned} x\in L\Leftrightarrow \exists y\in \{0,1\} ^{|x|^{d}}:(x,y)\in L'. \end{aligned}
  • \text {Op}=\forall
    \begin{aligned} x\in L\Leftrightarrow \forall y\in \{0,1\} ^{|x|^{d}}:(x,y)\in L'. \end{aligned}

With this notation we have: \text {NP}=\exists \cdot \text {P}, \text {BPP}=\text {BP}\cdot \text {P}, \Sigma _{2}\text {P}=\exists \cdot \forall \cdot \text {P}.

6.5 PH is a random low-degree polynomial

In this section we prove the following result.

Theorem 6.4. [37] \text {PH}\subseteq \text {BP}\cdot \oplus \cdot \text {P}.

This is saying that any constant number of \exists and \forall quantifier can be replaced by a BP quantifier followed by a \oplus quantifier. Let’s see what this has to do with the title of this section. Where is the polynomial? Consider polynomials over \mathbb {F}_{2}\in \{0,1\} . Recall that such a polynomial over n bits is an object like

\begin{aligned} p(x_{1},x_{2},\ldots ,x_{n})=x_{1}\cdot x_{2}+x_{3}+x_{7}\cdot x_{2}\cdot x_{1}+x_{2}+1. \end{aligned}

Because we are only interested in inputs in \{0,1\} we have x^{i}=x for any i\ge 1 and any variable x, so we don’t need to raise variables to powers bigger than one.

Example 6.1. The And function on n bits can be written as the polynomial

\begin{aligned} \text {And}(x_{1},x_{2},\ldots ,x_{n})=\prod _{i=1}^{n}x_{i}. \end{aligned}

The Or function on n bits can be written as the polynomial

\begin{aligned} \text {Or}(x_{1},x_{2},\ldots ,x_{n})=1+\text {And}(1+x_{1},1+x_{2},\ldots ,1+x_{n})=1+\prod _{i=1}^{n}(1+x_{i}). \end{aligned}

For n=2 we have

\begin{aligned} \text {Or}(x_{1},x_{2})=x_{1}+x_{2}+x_{1}\cdot x_{2}. \end{aligned}

The polynomial corresponding to a PH computation will have an exponential number of terms, so we can’t write it down. The big sum over all its monomials corresponds to the \oplus in Theorem 6.4. The polynomial will be sufficiently explicit: we will be able to compute each of its monomials in P. Finally, there won’t be just one polynomial, but we will have a distribution on polynomials, and that’s the BP part.

Confusing? Like before, a good way to look at this result is in terms of alternating circuits. We state the basic circuit result behind Theorem 6.4 after a definition. The result is of independent interest and will be useful later.

Definition 6.4. A distribution P on polynomials computes a function f:\zonzo with error \epsilon if for every x we have

\begin{aligned} \mathbb {P}_{P}[P(x)=f(x)]\ge 1-\epsilon . \end{aligned}

Theorem 6.5. Let C:\{0,1\} ^{n}\to \{0,1\} be an alternating circuit of depth d and size s. Then there is a distribution P on polynomials over \mathbb {F}_{2} of degree \log ^{d}s/\epsilon that computes C with error \epsilon .

Ultimately we only need constant error, but the construction requires small error. Jumping ahead, this is because we construct distributions for each gate separately, and we need the error to be small enough for a union bound over all gates in the circuit.

The important point in Theorem 6.5 is that if the depth d is small (e.g., constant) (and the size is not enormous and the error is not too small) then the degree is small as well. For example, for power-size alternating circuits of constant depth the degree is power logarithmic for constant error.

Let us slowly illustrate the ideas behind Theorem 6.5 starting with the simplest case: C is just a single Or gate on n bits.

Lemma 6.5. For every \epsilon and n there is a distribution P on polynomials of degree \log 1/\epsilon in n variables over \mathbb {F}_{2} that computes Or with error \epsilon .

Proof. For starters, pick the following distribution on linear polynomials: For a uniform A=(A_{1},A_{2},\ldots ,A_{n})\in \{0,1\} ^{n} output the polynomial

\begin{aligned} p_{A}(x_{1},x_{2},\ldots ,x_{n}):=\sum _{i}A_{i}\cdot x_{i}. \end{aligned}

Let us analyze how p_{A} behaves on a fixed input x\in \{0,1\} ^{n}:

  • If \text {Or}(x)=0 then p_{A}(x)=0;
  • If \text {Or}(x)=1 then \mathbb {P}_{A}[p_{A}(x)=1]\ge 1/2.

While the error is large in some cases, a useful feature of p_{A} is that it never makes mistakes if \text {Or}(x)=0. This allows us to easily reduce the error by taking t:=\log 1/\epsilon polynomials p_{A} and combining them with an Or.

\begin{aligned} p_{A_{1},A_{2},\ldots ,A_{t}}(x):=p_{A_{1}}(x)\vee p_{A_{2}}(x)\vee \cdots \vee p_{A_{t}}(x). \end{aligned}

The analysis is like before:

  • If \text {Or}(x)=0 then p_{A_{1},A_{2},\ldots ,A_{t}}(x)=0;
  • If \text {Or}(x)=1 then \mathbb {P}_{A_{1},A_{2},\ldots ,A_{t}}[p{}_{A_{1},A_{2},\ldots ,A_{t}}(x)=1]\ge 1-(1/2)^{t}\ge 1-\epsilon .

It remains to bound the degree. Each p_{A_{i}} has degree 1. The Or on t bits has degree t by Example 6.1. Hence the final degree is t=\log 1/\epsilon . QED

Exercise 6.10. Obtain the same result for C=\text {And}.

Now we would like to handle general circuits which have any number of And and Or gates. As mentioned earlier, we apply the construction above to every gate, and compose the polynomials. We pick the error at each gate small enough so that we can do a union bound over all gates.

Proof of Theorem 6.5.  We apply Lemma 6.5 to every gate in the circuit with error \epsilon /s. By a union bound, the probability that any gate makes a mistake is \epsilon , as desired.

The final polynomial is obtained by composing the polynomials of each gate. The composition of a polynomial of degree d_{1} with another of degree d_{2} results in a polynomial of degree d_{1}\cdot d_{2}. Since each polynomial has degree \log s/\epsilon , the final degree is \log ^{d}s/\epsilon . QED

6.5.1 Back to PH

We have proved Theorem 6.5 which is a circuit analogue of Theorem 6.4. We now go back to the PH. First, we have to come up with a more explicit description of the polynomials, instead of picking them at random. This is similar to the way we proceeded in section º6.3: After a non-explicit construction (Lemma 6.3) we then obtained an explicit construction (Lemma 6.4).

Let us go back to the simplest case of Or. Recall that the basic building block in the proof of Lemma 6.5 was the construction of a distribution p_{A} on linear polynomials which are zero on the all-zero input (which just means that they do not have constant terms), and are often non-zero on any non-zero input. We introduce a definition, since now we will have several constructions with different parameters.

Definition 6.5. A distribution p_{A} on linear polynomials with no constant term has the Or property if \mathbb {P}_{A}[p_{A}(x)=1]\ge 1/3 for any x\ne 0. We identify p_{A} with the n bits A corresponding to its coefficients.

The next lemma shows that we can compute distributions on linear polynomials with the Or property from a seed of just \log n+c bits, as opposed to the n bits that were used for A in the proof of Lemma 6.5. Recall that for our application to Lemma 6.5 the polynomials have an exponential number of monomials and so we cannot afford to write them down. Instead we shall guarantee that given a seed r and an index to a monomial we can compute the monomial via a function f in P. In this linear case, for a polynomial in n variables we have \le n monomials x_{i}. So the function f takes as input r and a number i\le n and outputs the coefficient to x_{i}.

Lemma 6.6. [25] Given n, i\le n, and r\in \{0,1\} ^{2\log n+c} we can compute in P a function f(r,i) such that for uniform R\in \{0,1\} ^{2\log n+c} the distribution

\begin{aligned} (f(R,1),f(R,2),\ldots ,f(R,n)) \end{aligned}

has the Or property.

Proof. [4] Let q:=2^{\log n+c} and identify the field \mathbb {F}_{q} with bit strings of length \log q. We view r as a pair (s,t)\in (\mathbb {F}_{q})^{2}. Then we define

\begin{aligned} f((s,t),i):=\langle s^{i},t\rangle \end{aligned}

where s^{i} is exponentiation in \mathbb {F}_{q} and \langle .,.\rangle :(\mathbb {F}_{q})^{2}\to \{0,1\} is defined as \langle u,v\rangle :=\sum u_{i}\cdot v_{i} over \mathbb {F}_{2}.

To show that this has the Or property, pick any non-zero x\in \{0,1\} ^{n}. We have to show that

\begin{aligned} p:=\mathbb {P}_{S,T}[\sum _{i}\langle S^{i},T\rangle x_{i}=1]\ge 1/3. \end{aligned}

The critical step is to note that

\begin{aligned} \sum _{i}\langle S^{i},T\rangle x_{i}=\sum _{i}\langle x_{i}\cdot S^{i},T\rangle =\langle \sum _{i}x_{i}\cdot S^{i},T\rangle . \end{aligned}

Now, if x\ne 0, then the probability over S that \sum _{i}x_{i}\cdot S^{i}=0 is \le n/q\le 1/6. This is because any S that gives a zero is a root of the non-zero, univariate polynomial q(y):=\sum _{i}x_{i}\cdot y^{i} of degree \le n over \mathbb {F}_{q}, and so the bound follows by Theorem 5.8.

Whenever \sum _{i}x_{i}\cdot S^{i}\ne 0, the probability over T that \langle \sum _{i}x_{i}\cdot S^{i},T\rangle =0 is 1/2. Hence our target probability p above satisfies

\begin{aligned} p\ge 1/2-1/6 \end{aligned}

as desired. QED

Exercise 6.11. Give an alternative construction of a distribution with the Or property following this guideline.

(1) Satisfy the Or property for every input x with weight 1.

(2) For any j, satisfy the Or property for every input x with weight between 2^{j} and 2^{j+1}. Use Lemma 5.2.

(3) Combine (2) with various j to satisfy the Or property for every input.

(4) State the seed length for your distribution and compare it to that of Lemma 6.6.

With this in hand, we can now reduce the error in the same way we reduced it in the proof of Lemma 6.5.

Lemma 6.7. Given n, a seed r\in \{0,1\} ^{c\log (1/\epsilon )\log n}, and m\le n^{c\log 1/\epsilon } we can compute in P a monomial X_{r,m} of degree c\log 1/\epsilon such that the distribution

\begin{aligned} \sum _{m}X_{R,m} \end{aligned}

for uniform R computes Or with error \epsilon .

Proof. We use the construction

\begin{aligned} p_{A_{1},A_{2},\ldots ,A_{t}}(x):=p_{A_{1}}(x)\vee p_{A_{2}}(x)\vee \cdots \vee p_{A_{t}}(x) \end{aligned}

from the proof of Lemma 6.5, except that each A_{i} is now generated via Lemma 6.5, and that t=c\log 1/\epsilon (as opposed to t=\log 1/\epsilon before). The bound on the degree is the same as before, as is the proof that it computes Or: The error will be (1/3)^{c\log 1/\epsilon }\le \epsilon .

There remains to show that the monomials can be computed in P. For this we can go back to the polynomial for Or in Example 6.1. Plugging that gives

\begin{aligned} p_{A_{1},A_{2},\ldots ,A_{t}}(x)=\sum _{a\in \{0,1\} ^{t}:a\ne 0}\prod _{i\le t}(p_{A_{i}}(x)+a_{i}+1). \end{aligned}

We can use m to index a choice of a and then a choice for a monomial in each of the t linear factors p_{A_{i}}(x)+a_{i}+1. For each factor we can use Lemma 6.6 to compute the monomials. QED

We can now use Lemma 6.7 to prove Theorem 6.4. As in the proof Theorem 6.5 we will convert each gate to a polynomial.

Proof of Theorem 6.4.  Let L\in \text {PH}. Apply Lemma 6.2 to obtain a corresponding alternating circuit C of depth d and size s\le 2^{n^{d}} for a constant d. Replace each gate with the distribution on polynomials given by Lemma 6.7. Note each of these polynomials is on 2^{n^{c_{d}}}variables and has degree n^{c_{d}}. We set the error \epsilon in Lemma 6.7 to be 1/(3s). This guarantees that the seed length in each application of Lemma 6.7 is \le n^{c_{d}}. Moreover, the seed used to sample the polynomials is re-used across all gates. We can afford this because we use a union bound in the analysis. Hence the seed length for all the polynomials is again just n^{c_{d}}. We can quantify over this many bits using the BP quantifier.

Finally, we have to compose the polynomials at each gate. We are going to show how we can compute the monomials of the composed polynomial in the same way as we computed monomials in Lemma 6.7. Once we have a monomial in the input variables x_{1},x_{2},\ldots ,x_{n} we simply evaluate it in P on the input bits.

Start at the output gate. We use n^{c_{d}} bits in the \oplus quantifier to choose a monomial in the corresponding polynomial. We write down this monomial, using Lemma 6.7. This monomial is over the 2^{n^{d}} variables z_{1},z_{2},\ldots corresponding to the children of the output gate, and only contains n^{c_{d}} variables. To each z_{i} there corresponds a polynomial p_{i}. Choose a monomial from p_{i} and replace z_{i} with that monomial; do this for every i. The choice of the monomials is done again using bits quantified by the \oplus quantifier. We continue in this way until we have monomials just in the input variables x_{1},x_{2},\ldots ,x_{n}. Because each monomial is over n^{c_{d}} variables, and the depth is constant, the total number of bits in the \oplus quantifier, which are needed to choose monomials, is n^{c_{d}}. QED

Exercise 6.12. A set C\subseteq \{0,1\} ^{n} of size 2^{k} is called linear if there exists an n\times k matrix M over \mathbb {F}_{2} such that C=\{Mx:x\in \{0,1\} ^{k}\}.

  1. Recall error-correcting codes from Exercise 2.18. Prove that a linear set C is an error-correcting code iff the weight of any non-zero string in C is at least n/3.
  2. Prove the existence of linear error-correcting codes matching the parameters in Exercise 2.18.
  3. Let S be a subset of \{0,1\} ^{k} s.t. the uniform distribution over S has the Or property. Define |S|\times k matrix M_{S} where the rows are the elements of S. Prove that \{M_{S}x:x\in \{0,1\} ^{k}\} is an error-correcting code.
  4. Give explicit error-correcting codes over ck^{2} bits of size 2^{k}.
  5. This motivates improving the parameters of distributions with the Or property. Improve the seed length in Lemma 6.6 to \log n+c\log \log n. Hint: What property you need from T?
  6. Give explicit error-correcting codes over k\log ^{c}k bits of size 2^{k}.

6.6 The power of majority

Exercise 6.13. [The power of majority] Prove:

  1. \text {BPP}\cdot \text {P}\subseteq \text {Maj}\cdot \text {P}.
  2. \{(M,x,t):\text { the number of }y\in \{0,1\} ^{|t|}\text { such that }M(x,y)=1\text { is }\ge t\}\in \text {Maj}\cdot \text {P}.
  3. The same as 2. but with \ge replaced by \le .
  4. \text {NP}\subseteq \text {Maj}\cdot \text {P}.
  5. Maj \cdot \oplus \cdot \text {P}\subseteq \text {Maj}\cdot \text {Maj}\cdot \text {P}. (Hint: This is confusing if you don’t have the right angle, otherwise is not too bad. For starters, forget everything and imagine you have an integer w in some range and you want to know if w is odd by just asking questions of the type w\ge t and w\le t', for various t,t'. You want that the number of questions with answer “yes” only depends on whether w is odd or even.)
  6. \text {PH}\subseteq \text {Maj}\cdot \text {Maj}\cdot \text {P}.

It is not known if \text {NP} has linear-size circuits. We saw in Exercise 6.4 that PH does not have circuits of size n^{k}, for any k. By Exercise 6.13 this holds for \text {Maj}\cdot \text {Maj}\cdot \text {P} as well. The following result improves this Maj \cdot P. It is particularly interesting because it cannot be established using a well-studied class of techniques which includes all the results about PH we have encountered so far.

Theorem 6.6. [40] \text {Maj}\cdot \text {P}\not \subseteq \text {CktGates}(n^{k}), for any k\in \mathbb {N}.

References

[1]   Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 59–78. IEEE Computer Society, 2015.

[2]   Leonard Adleman. Two theorems on random polynomial time. In 19th IEEE Symp. on Foundations of Computer Science (FOCS), pages 75–83. 1978.

[3]   Mikl≤s Ajtai. \Sigma \sp {1}\sb {1}-formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1–48, 1983.

[4]   Noga Alon, Oded Goldreich, Johan Hσstad, and RenΘ Peralta. Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992.

[5]   Dana Angluin and Leslie G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. J. Comput. Syst. Sci., 18(2):155–193, 1979.

[6]   Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. of the ACM, 45(3):501–555, May 1998.

[7]   Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM J. Comput., 47(3):1087–1097, 2018.

[8]   Kenneth E. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Computing Conference, volume 32, pages 307–314, 1968.

[9]   Stephen A. Cook. A hierarchy for nondeterministic time complexity. J. of Computer and System Sciences, 7(4):343–353, 1973.

[10]   Aviezri S. Fraenkel and David Lichtenstein. Computing a perfect strategy for n x n chess requires time exponential in n. J. Comb. Theory, Ser. A, 31(2):199–214, 1981.

[11]   Anka Gajentaan and Mark H. Overmars. On a class of {O}(n^2) problems in computational geometry. Comput. Geom., 5:165–185, 1995.

[12]   M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

[13]   K. G÷del. ▄ber formal unentscheidbare sΣtze der Principia Mathematica und verwandter systeme I. Monatsh. Math. Phys., 38, 1931.

[14]   Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.

[15]   David Harvey and Joris van der Hoeven. Integer multiplication in time O(n\mathrm {log}\, n). Annals of Mathematics, 193(2):563 – 617, 2021.

[16]   F. C. Hennie. One-tape, off-line turing machine computations. Information and Control, 8(6):553–578, 1965.

[17]   Fred Hennie and Richard Stearns. Two-tape simulation of multitape turing machines. J. of the ACM, 13:533–546, October 1966.

[18]   Russell Impagliazzo and Ramamohan Paturi. The complexity of k-sat. In IEEE Conf. on Computational Complexity (CCC), pages 237–, 1999.

[19]   Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Computer & Systems Sciences, 63(4):512–530, Dec 2001.

[20]   Russell Impagliazzo and Avi Wigderson. \mathit {P} = \mathit {BPP} if E requires exponential circuits: Derandomizing the XOR lemma. In 29th ACM Symp. on the Theory of Computing (STOC), pages 220–229. ACM, 1997.

[21]   Richard M. Karp and Richard J. Lipton. Turing machines that take advice. L’Enseignement MathΘmatique. Revue Internationale. IIe SΘrie, 28(3-4):191–209, 1982.

[22]   Kojiro Kobayashi. On the structure of one-tape nondeterministic turing machine time hierarchy. Theor. Comput. Sci., 40:175–193, 1985.

[23]   Leonid A. Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):115–116, 1973.

[24]   O. B. Lupanov. A method of circuit synthesis. Izv. VUZ Radiofiz., 1:120–140, 1958.

[25]   Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. on Computing, 22(4):838–856, 1993.

[26]   NEU. From RAM to SAT. Available at http://www.ccs.neu.edu/home/viola/, 2012.

[27]   Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3):425–440, 1991.

[28]   Wolfgang J. Paul, Nicholas Pippenger, Endre SzemerΘdi, and William T. Trotter. On determinism versus non-determinism and related problems (preliminary version). In IEEE Symp. on Foundations of Computer Science (FOCS), pages 429–438, 1983.

[29]   Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. of the ACM, 26(2):361–381, 1979.

[30]   J. M. Robson. N by N checkers is exptime complete. SIAM J. Comput., 13(2):252–267, 1984.

[31]   Rahul Santhanam. On separators, segregators and time versus space. In IEEE Conf. on Computational Complexity (CCC), pages 286–294, 2001.

[32]   Arnold Sch÷nhage. Storage modification machines. SIAM J. Comput., 9(3):490–508, 1980.

[33]   Claude E. Shannon. The synthesis of two-terminal switching circuits. Bell System Tech. J., 28:59–98, 1949.

[34]   Victor Shoup. New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54(189):435–447, 1990.

[35]   Michael Sipser. A complexity theoretic approach to randomness. In ACM Symp. on the Theory of Computing (STOC), pages 330–335, 1983.

[36]   Larry Stockmeyer and Albert R. Meyer. Cosmological lower bound on the circuit complexity of a small problem in logic. J. ACM, 49(6):753–784, 2002.

[37]   Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. on Computing, 20(5):865–877, 1991.

[38]   Alan M. Turing. On computable numbers, with an application to the entscheidungsproblem. Proc. London Math. Soc., s2-42(1):230–265, 1937.

[39]   Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theor. Comput. Sci., 47(3):85–93, 1986.

[40]   N. V. Vinodchandran. A note on the circuit complexity of PP. Theor. Comput. Sci., 347(1-2):415–418, 2005.

[41]   Emanuele Viola. On approximate majority and probabilistic time. Computational Complexity, 18(3):337–375, 2009.

[42]   Emanuele Viola. Reducing 3XOR to listing triangles, an exposition. Available at http://www.ccs.neu.edu/home/viola/, 2011.

[43]   Emanuele Viola. Pseudorandom bits and lower bounds for randomized turing machines. Theory of Computing, 18(10):1–12, 2022.