Mathematics of the impossible: Computational Complexity, chapter 4, reductions

Thoughts 2023-02-09

All posts in this series. A PDF version of this post will be published with a delay, but if you’d like to have it soon let me know.

4 Reductions 4.1 Types of reductions 4.2 Reductions 4.2.1 Multiplication 4.2.2 3Sum 4.3 Reductions from 3Sat 4.4 Power hardness from SETH 4.5 Search problems 4.5.1 Fastest algorithm for Search-3Sat 4.6 Gap-SAT: The PCP theorem 4.7 Problems

Chapter 4 Reductions

https://xkcd.com/230/

One can relate the complexity of functions via reductions. This concept is so ingrained in common reasoning that giving it a name may feel, at times, strange. For in some sense pretty much everything proceeds by reductions. In any algorithms textbook, the majority of algorithms can be cast as reductions to algorithms presented earlier in the book, and so on. And it is worthwhile to emphasize now that, as we shall see below, reductions, even in the context of computing, have been used for millennia. For about a century reductions have been used in the context of undecidability in a modern way, starting with the incompleteness theorem in logic [8], whose proof reduces questions in logic to questions in arithmetic.

Perhaps one reason for the more recent interest in complexity reductions is that we can use them to relate problems that are tantalizingly close to problems that today we solve routinely on somewhat large scale inputs with computers, and that therefore appear to be just out of reach. By contrast, reductions in the context of undecidability tend to apply to problems that are completely out of reach, and in this sense remote from our immediate worries.

4.1 Types of reductions

Informally, a reduction from a function $f$ to a function $g$ is a way to compute $f$ given that we can compute $g$ . One can define reductions in different ways, depending on the overhead required to compute $f$ given that we can compute $g$ . The most general type of reduction is simply an implication.

General form of reduction from $f$ to $g$ :

If $g$ can be computed with resources $X$ then $f$ can be computed with resources $Y$ .

A common setting is when $X=Y$ . In this case the reduction allows us to stay within the same complexity class.

Definition 4.1. We say that $f$ reduces to $g$ in $X$ (or under $X$ reductions) if

$\begin{aligned} g\in X\Rightarrow f\in X. \end{aligned}$

A further special and noteworthy case is when $X=\text {P}$ , or $X=\text {BPP}$ ; in these cases the reduction can be interpreted as saying that if $g$ is easy to compute than $f$ is too.But in general $X$ may not be equal to $Y$ . We will see examples of such implications for various $X$ and $Y$ .

It is sometimes useful to be more specific about how the implication is proved. For example, this is useful when inferring various properties of $f$ from properties of $g$ , something which can be obscured by a stark implication. The following definition gives a specific way in which the implication can be proved.

Definition 4.2. We say that $f$ map reduces to $g$ in $X$ (or via a map in $X$ ) if there is $M\in X$ such that $f(x)=g(M(x))$ for every $x$ .

Exercise 4.1. Suppose that $f$ map reduces to $g$ in $X$ .

(1) Suppose $X=\text {P}$ . Show $f$ reduces to $g$ in $\text {X}$ .

(2) Suppose $X=\bigcup _{d}\text {Time}(d\cdot n^{2})$ . Can you still show that $f$ reduces to $g$ in $\text {X}$ ?

Many reductions we shall see are not mapping reductions. In fact, our first example is not a mapping reduction.

4.2 Reductions

4.2.1 Multiplication

Summing two $n$ -bit integers is in $\text {CktGates}(cn)$ (Exercise 2.8). But the smallest circuit known for multiplication has $\ge cn\log n$ gates [10]. (The same situation holds for MTMs; over RAMs and related models multiplication can be done in time $cn$ [21].) It is a long-standing question whether we can multiply two $n$ -bit integers with a linear-size circuit.

What about squaring integers? Is that harder or easier than multiplication? Obviously, if we can multiply two numbers we can also square a number: simply multiply it by itself. This is a trivial example of a reduction. What about the other way around? We can use a reduction established millennia ago by the Babylonians. They employed the equation

$\begin{aligned} a\cdot b=\frac {(a+b)^{2}-(a-b)^{2}}{4}~~~~(4.1) \end{aligned}$

to reduce multiplication to squaring, plus some easy operations like addition and division by four. In our terminology we have the following.

Definition 4.3. Multiplication is the problem of computing the product of two $n$ -bit integers. Squaring is the problem of computing the square of an $n$ -bit integer.

Theorem 4.1. If Squaring has linear-size circuits then Multiplication has linear-size circuits.

Proof. Suppose $C$ computes Squaring. Then we can multiply using equation (??). Specifically, given $a$ and $b$ we use Exercise 2.8 to compute $a+b$ and $a-b$ . (We haven’t seen subtraction or negative integers, but it’s similar to addition.) Then we run $C$ on both of them. Finally, we again use Exercise 2.8 for computing their difference. It remains to divide by four. In binary, this is accomplished by ignoring the last two bits – which costs nothing on a circuit. QED

4.2.2 3Sum

Definition 4.4. The $3\text {Sum}$ problem: Given a list of integers, are there three integers that sum to $0$ ?

It is easy to solve 3Sum in time $cn^{2}\log n$ on a RAM. (We can first sort the integers then for each pair $(a,b)$ we can do a binary search to check if $-(a+b)$ is also present.) The time can be improved $n^{2}/\log ^{c}n$ .

3Sum is believed to require quadratic time.

Definition 4.5. $\text {SubquadraticTime}:=\bigcup _{\epsilon >0}\text {Time}(n^{2-\epsilon })$ .

Conjecture 4.1. $\text {3Sum}\not \in \text {SubquadraticTime}$ .

One can reduce 3Sum to a number of other interesting problem to infer that, under Conjecture 4.1, those problems require quadratic time too.

Definition 4.6. The Collinearity problem: Given a list of points in the plane, are there three points on a line?

Theorem 4.2. [6] $\text {Collinearity}\in \text {SubquadraticTime\ensuremath {\Rightarrow \text {3Sum}\in \text {SubquadraticTime}} (i.e., }$ Conjecture 4.1 is false).

Proof. We map instance $a_{1},a_{2},\ldots ,a_{n}$ of 3Sum to the points

$\begin{aligned} (a_{1},a_{1}^{3}),(a_{2},a_{2}^{3}),\ldots ,(a_{n},a_{n}^{3}), \end{aligned}$

and solve Collinearity on those points.

To verify correctness, notice that points $(x,x^{3}),(y,y^{3}),$ and $(z,z^{3})$ are on a line iff

$\begin{aligned} \frac {y^{3}-x^{3}}{y-x}=\frac {z^{3}-x^{3}}{z-x}. \end{aligned}$

Because $y^{3}-x^{3}=(y-x)(y^{2}+yx+x^{2})$ , this condition is equivalent to

$\begin{aligned} y^{2}+yx+x^{2}=z^{2}+zx+x^{2}\Leftrightarrow (x+(y+z))(y-z). \end{aligned}$

Assuming $y\ne z$ , i.e., that the 3Sum instance consists of distinct numbers, this is equivalent to $x+y+z=0$ , as desired. (The case where there can be duplicates is left as an exercise.)

Note that the Collinearity instance has length linear in the 3Sum instance, and the result follows. QED

Exercise 4.2. The Tripartite-3Sum problem: Given lists $A_{1}$ , $A_{2}$ , and $A_{3}$ of numbers, are there $a_{i}\in A_{i}$ s.t. $a_{1}+a_{2}+a_{3}=0?$

Prove that Tripartite-3Sum is in subquadratic time iff 3Sum is.

We now give a reduction in the other direction: We reduce a problem to 3Sum.

Definition 4.7. The 3Cycle-Detection problem: Given the adjacency list of a directed graph, is there a cycle of length 3?

This problem can be solved in time $n^{2\omega /(\omega +1)+o(1)}$ where $\omega <2.373$ is the exponent of matrix multiplication. If $\omega =2$ then the bound is $n^{1.3\bar {3}+o(1)}$ . It is not known if any subquadratic algorithm for 3Sum would improve these bounds. However, we can show that an improvement follows if $\text {3Sum}\in \text {Time}(n^{1+\epsilon})$ for a small enough $\epsilon$ .

Theorem 4.3. [26] $\text {3Sum}\in \text {Time}(t(n))\Rightarrow \text {3Cycle-Detection}\in \text {BPTime}(ct(n)),$ for any $t(n)\ge n$ .

The reduction can be derandomized (that is, one can replace $\text {BPTime}$ with $\text {Time}$ in the conclusion) but the randomized case contains the main ideas.

Proof. We assign random numbers $r_{x}$ with $4\log n$ bits to each node $x$ in the graph. The 3Sum instance consists of the integers $r_{x}-r_{y}$ for every edge $x\to y$ in the graph.

To verify correctness, suppose that there is a cycle

$\begin{aligned} x\to y\to z\to x \end{aligned}$

in the graph. Then we have $r_{x}-r_{y}+r_{y}-r_{z}+r_{z}-r_{x}=0$ , for any random choices.

Conversely, suppose there is no cycle, and consider any three numbers $r_{x1}-r_{y1},r_{x2}-r_{y2},r_{x3}-r_{y3}$ from the reduction and its corresponding edges. Some node $xi$ has unequal in-degree and out-degree in those edges. This means that when summing the three numbers, the random variable $r_{xi}$ will not cancel out. When selecting uniform values for that variable, the probability of getting $0$ is at most $1/n^{4}$ .

By a union bound, the probability there there are three numbers that sum to zero is $\le n^{3}/n^{4}<1/3.$ QED

Exercise 4.3. Prove an analogous result for undirected graphs. Note TBD: This exercise should be more interesting for 4-cycles, because you can’t just duplicate edges, I think.

Many other clusters of problems exist, for example based on matrix multiplication or all-pairs shortest path.

4.3 Reductions from 3Sat

In this section we begin to explore an important cluster of problems not known to be in $\text {BPP}$ . What’s special about these problems is that in Chapter ?? we will show that we can reduce arbitrary computation to them, while this is unknown for the problems in the previous section.

Perhaps the most basic problem in the cluster is the following.

Definition 4.8. The 3Sat problem: Given a 3CNF $\phi$ , is there an assignment $x$ s.t. $\phi (x)=1$ ?

Conjecture 4.2. $\text {3Sat\ensuremath {\not }\ensuremath {\ensuremath {\in \text {P}}}.}$

Stronger conjectures have been made.

Conjecture 4.3. [13] [Exponential time hypothesis (ETH)] There is $\epsilon>0$ such that there is no algorithm that on input a $3$ CNF $\phi$ with $v$ variables and $cv^{3}$ clauses decides if $\phi$ is satisfiable in time $2^{(\epsilon +o(1))v}$ .

Conjecture 4.4. [14] [Strong exponential-time hypothesis (SETH)] For every $\epsilon >0$ there is $k$ such that there is no algorithm that on input a $k$ CNF $\phi$ with $v$ variables and $cv^{k}$ clauses decides if $\phi$ is satisfiable in time $2^{(1-\epsilon +o(1))v}$ .

It is known that $\text {SETH}\Rightarrow \text {ETH},$ but the proof is not immediate.

We now give reductions from 3Sat to several other problems. The reductions are in fact mapping reductions. Moreover, the reduction map can be extremely restricted, see Problem 4.4. In this sense, therefore, this reduction can be viewed as a direct translation of the problem, and maybe we shouldn’t really be thinking of the problems as different, even if they at first sight refer to different types of objects (formulas, graphs, numbers, etc.).

Watch videos 29, 30, 31, and 32 covering reductions: 3SAT to CLIQUE, CLIQUE to VERTEX-COVER, 3SAT to SUBSET-SUM, 3SAT to 3COLOR from https://www.ccs.neu.edu/home/viola/classes/algm-generic.html

Note: The videos use the terminology “polynomial time” instead of “power time” here.

Exercise 4.4. The problem System is defined as follows. A linear inequality is an inequality involving sums of variables and constants, such as $x+y\ge z$ , $x\le -17$ , and so on. A system of linear inequalities has an integer solution if it is possible to substitute integer values for the variables so that every inequality in the system becomes true. The language System consists of systems of linear inequalities that have an integer solution. For example,

$\begin{aligned} (x+y\ge z,x\le 5,y\le 1,z\ge 5)\in \mbox {System }\\ (x+y\ge 2z,x\le 5,y\le 1,z\ge 5)\not \in \mbox {System } \end{aligned}$

Reduce 3Sat to System in $\text {P}$ .

Exercise 4.5. For an integer $k$ , $k$ -Color is the problem of deciding if the nodes of a given undirected graph $G$ can be colored using $k$ colors in such a way that no two adjacent vertices have the same color.

Reduce 3-Color to 4-Color P.

Reductions in the opposite directions are possible, and so in fact the problems in this section are power-time equivalent in the sense that any of the problems is in $\text {P}$ iff all the others are. We will see a generic reduction in the next chapter. For now, we illustrate this equivalence in a particular case.

Exercise 4.6. Reduce 3Color to 3Sat in $\text {P}$ , following these steps:

1. Given a graph $G$ , introduce variables $x_{i,c}$ representing that node $i$ has color $c$ , where $c$ ranges in the set of colors $C=\{g,r,b\}$ . Describe a set of clauses that is satisfiable if and only if for every $i$ there is exactly one $c\in C$ such that $x_{i,c}$ is true.

2. Introduce clauses representing that adjacent nodes do not have the same color.

3. Briefly conclude the proof.

Thus, we are identifying a cluster of problems which are all power-time equivalent. This cluster is so prominent that problems in it have been compiled into books [7]. More recently, it was shown that it contains (generalized versions of) several games including: Tetris, Lemmings, Sudoku, etc. For a list see e.g. the wikipedia page https://en.wikipedia.org/wiki/List_of_NP-complete_problems

4.4 Power hardness from SETH

In this section we show that a conjecture similar to Conjecture 4.1 can be proved assuming SETH. This is an interesting example of how we can connect different parameter regimes, since SETH is stated in terms of exponential running times. In general, “scaling” parameters is a powerful technique in the complexity toolkit.

Definition 4.9. The Or-Vector problem: Given two sets $A$ and $B$ of strings of the same length, determine if there is $a\in A$ and $b\in B$ such that the bit-wise Or $a\vee b$ equals the all-one vector.

The Or-Vector problem is in $\text {Time}(n^{2})$ . We can show that a substantial improvement would disprove SETH.

Theorem 4.4. $\text {Or-Vector}\in \text {SubquadraticTime}\Rightarrow \text {SETH is false.}$

Proof. Divide the variables in two blocks of $v/2$ each. For each assignment to the variables in the first block construct the vector in $\{0,1\} ^{d}$ where bit $i$ is $1$ iff clause $i$ is satisfied by the variables in the first block. Call $A$ the resulting set of vectors. Let $N:=2^{v/2}$ and note $|A|=N$ . Do the same for the other block and call the resulting set $B$ .

Note that $\phi$ is satisfiable iff $\exists a\in A,b\in B$ such that $a\vee b=1^{d}$ .

Constructing these sets takes time $Nd^{c}$ . If $\text {Or-Vector}\in \text {Time}(n^{2-\epsilon })$ for some $\epsilon >0$ , we can take $k=c_{\epsilon}$ and rule out SETH. QED

Tight hardness results based on SETH have been established for several well-studied problems, including longest-common subsequence [1] and edit distance [5].

4.5 Search problems

Most of the problems in the previous sections ask about the existence of solutions. For example 3Sat asks about the existence of a satisfying assignment. It is natural to ask about computing such a solution, if it exists. Such non-boolean problems are known as search problems.

Next we show that in some cases we can reduce a search problem to the corresponding boolean problem.

Definition 4.10. Search-3Sat is the problem: Given a satisfiable 3CNF formula, output a satisfying assignment.

Theorem 4.5. Search-3Sat reduces to 3Sat in $\text {P}$ . That is: $\text {3Sat}\in \text {P}\Rightarrow \text {Search-3Sat}\in \text {P}$ .

Proof. We construct a satisfying assignment one variable at the time. Given a satisfiable 3CNF, set the first variable to $0$ and check if it is still satisfiable with the assumed algorithm for 3Sat. If it is, go to the next variable. If it is not, set the first variable to $1$ and go to the next variable. QED

Exercise 4.7. Show $\text {Clique}\in \text {P}\Rightarrow \text {Search-Clique}\in \text {P}$ .

4.5.1 Fastest algorithm for Search-3Sat

A curious fact about many search problems is that we know of an algorithm which is, in an asymptotic sense to be discussed now, essentially the fastest possible algorithm. This algorithm proceeds by simulating every possible program. When a program stops and outputs the answer, we can check it efficiently. Naturally, we can’t just take any program and simulate it until it ends, since it may never end. So we will clock programs, and stop them if they take too long. There is a particular simulation schedule which leads to efficient running times.

Theorem 4.6. [17] There is a RAM $U$ such that on input any satisfiable formula $x$ :

(1) $M$ outputs a satisfying assignment, and

(2) If there is a RAM $M$ that on input $x$ outputs a satisfying assignment for $x$ in $t$ steps then $U$ stops in $c_{M}t+|x|^{c}$ steps.

We are taking advantage of the RAM model. On other models it is not known if the dependence on $t$ can be linear.

Proof. For $i=1,2,\ldots$ the RAM $U$ simulates RAM $i$ for $2^{i}$ steps. 2.2 guarantees that for each $i$ the simulation takes time $c2^{i}$ . If RAM $i$ stops and outputs $y$ , then $U$ checks in time $|x|^{c}$ if $y$ is a satisfying assignment. If it is, then $U$ outputs $y$ and stops. Otherwise it continues.

Now let $M$ be as in (2). As before, we work with an enumeration of programs where each program appears infinitely often. Hence we can assume that $M$ has a description of length $\ell :=c_{M}+\log t$ . Thus the simulation will terminate when $i=\ell$ .

The time spent by $U$ for a fixed $i$ is $\le c\cdot 2^{i}+|x|^{c}$ . Hence he total running time of $U$ is

$\begin{aligned} \le c\sum _{j=1}^{\ell }\left (c2^{j}+|x|^{c}\right )\le c_{M}2^{\ell }+c_{M}|x|^{c}\le c_{M}(t+|x|^{c}). \end{aligned}$

QED

This result nicely illustrates how “constant factors” can lead to impractical results because, of course, the problem is that the constant in front of $t$ is enormous. Specifically, it is exponential in the size of the program, see Problem 4.5.

4.6 Gap-SAT: The PCP theorem

“Furthermore, most problem reductions do not create or preserve such gaps. There would appear to be a last resort, namely to create such a gap in the generic reduction [C]. Unfortunately, this also seems doubtful. The intuitive reason is that computation is an inherently unstable, non-robust mathematical object, in the sense that it can be turned from non-accepting by changes that would be insignificant in any reasonable metric – say, by flipping a single state to accepting.” [19]

One of the most exciting, consequential, and technical developments in complexity theory of the last few decades has been the development of reductions that create gaps.

Definition 4.11. $\gamma$ -Gap-3Sat is the 3Sat problem restricted to input formulas $f$ that are either satisfiable or such that any assignment satisfies at most a $\gamma$ fraction of clauses.

Note that 3Sat is equivalent to $\gamma$ -Gap-3Sat for $\gamma =1-1/n$ , since a formula of size $n$ has at most $n$ clauses. At first sight it is unclear how to connect the problems when $\gamma$ is much smaller. But in fact it is possible to obtain a constant $\gamma$ . This result is known as the PCP theorem, where PCP stands for probabilistically-checkable-proofs. The connection to proofs will be discussed in Chapter ??.

Theorem 4.7. [4] [PCP] There is $\gamma <1$ such that $\gamma \text {-Gap-3Sat}\in \text {P}\Rightarrow \text {3Sat}\in \text {P}$ .

Similar results can be established for other problems such as 3Color, but the reductions in the previous section don’t preserve gaps and can’t be immediately applied.

A major application of the PCP theorem is in inapproximability results. A typical optimization problem is Max-3Sat.

Definition 4.12. The Max-3Sat problem: given a 3CNF formula, find a satisfying assignment that satisfies the maximum number of clauses.

Solving 3Sat reduces to Max-3Sat (in Chapter ?? we will give a reverse reduction as well). But we can ask for $\beta$ -approximating Max-3Sat, that is, computing an assignment that satisfies a number of clauses that is at least a $\beta$ fraction of the maximum possible clauses that can be satisfied.

The PCP Theorem 4.7 implies that 3Sat reduces to $\beta -$ approximating Max-3Sat, for some constant $\beta <1$ .

It has been a major line of research to obtain tight approximation factors $\beta$ for a variety of problems. For example, 3Sat reduces to $\beta$ -approximating Max-3Sat for any $\b >7/8$ . This constant is tight because a random uniform assignment to the variables satisfies each clause with probability $7/8$ and hence expects to satisfy a $7/8$ fraction of the clauses.

Exercise 4.8. Turn this latter observation in an efficient randomized algorithm with an approximation factor $7/8-o(1)$ .

4.7 Problems

Problem 4.1. Reduce 3Sat to the PIT problem (Definition 2.8) over the field with two elements.

Problem 4.2. Prove that 3Sat is not $\text {TM-Time}(n^{1.99})$ . (Hint: Consider the Padded-Palindromes problem which is like palindromes except the input is divided in blocks of $c\log n$ bits, and only the first bit of each block may be non-zero. (1) Prove a time lower bound for Padded-Palindromes by explaining what modifications are needed to the proof of Theorem 3.1. (2) Give a suitable reduction from Padded-Palindromes to 3Sat.)

Problem 4.3. Show that $\text {3Color}\in \text {P}\Rightarrow \text {Search-3Color}\in \text {P}$ .

Problem 4.4. Give an encoding of 3Sat so that the reduction to 3Color in section º4.3 can be computed, for any input length, by a $1$ -local map (in particular, a circuit of constant depth).

Problem 4.5. Suppose there exists $a$ such that Theorem 4.6 holds with the running time of $U$ replaced with $(|M|\cdot t\cdot |x|)^{a}$ . (That is, the dependence on the program description improved to polynomial, and we allow even weaker dependence on $t$ .) Prove that $\text {3Sat}\in \text {P}$ .

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] Dana Angluin and Leslie G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. J. Comput. Syst. Sci., 18(2):155–193, 1979.

[4] 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.

[5] 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.

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

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

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

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

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

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

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

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

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

[15] 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.

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

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

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

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

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

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

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

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

[24] 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.

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

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

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