In this chapter we show how to reduce arbitrary computation to 3Sat (and hence to the other problems in section º4.3). What powers everything is the following landmark and, in hindsight, simple result which reduces circuit computation to 3Sat.
Theorem 5.1. Given a circuit with gates we can compute in a 3CNF formula in variables such that for every :
The key idea to guess computation and check it efficiently, using that computation is local. The additional variables one introduces contain the values of the gates during the computation of on . We simply have to check that they all correspond to a valid computation, and this can be written as 3CNF because each gate depends on at most two other gates.
Proof. Introduce a variable for each non-input gate in . The value of is intended to be the value of gate during the computation. Whether the value of a gate is correct is a function of variables: and the gates that input , some of which could be input variables. This can be written as a 3CNF by Theorem 2.3. Take an And of all these 3CNFs. Finally, add clause for the output gate . QED
Exercise 5.1. Write down the 3CNF for the circuit in figure 2.2, as given by the proof of Theorem 5.1.
Theorem 5.1 is a depth-reduction result. Indeed, note that a 3CNF can be written as a circuit of depth , whereas the original circuit may have any depth. This is helpful for example if you don’t have the depth to run the circuit yourself. You can let someone else produce the computation, and you can check it in small depth.
We can combine Theorem 5.1 with the simulations in Chapter 2 to reduce computation in other models to 3SAT. In particular, we can reduce MTMs running in time to 3Sat of size . To obtain such parameters we need the quasilinear simulation of MTMs by circuits, Theorem 2.5.
However, recall that a quasilinear simulation of RAMs by circuits is not known. Only a power simulation is (which is obtained by combining the power simulation of RAMs by MTMs, Theorem 2.6, with a simulation of MTMs by circuits). This would reduce RAM computation running in time to 3CNFs of size . We content ourselves with this power loss for the beginning of this chapter. Later in section º5.3 we will obtain a quasi-linear simulation using an enjoyable argument which also bypasses Theorem 2.5.
In fact, these simulations apply to a more general, non-deterministic, model of computation. We define this model next, and then present the simulation with power loss in 5.2.
5.1 Nondeterministic computation
In the concluding equation in Theorem 5.1 there is an quantifier on the right-hand side, but there isn’t one on the left, next to the circuit. However, because the simulation works for every input, we can “stick” a quantifier on the left and have the same result. The resulting circuit computation has two inputs, and . We can think of it as a non-deterministic circuit, which on input outputs iff . Following the discussion before, we could do the same for other models like TMs, MTMs, and RAMs. The message here is that – if we allow for an quantifier, or in other words consider nondeterministic computation – efficient computation is equivalent to 3CNF! This is one motivation for formally introducing a nondeterministic computational model.
Definition 5.1. NTime is the set of functions for which there is a RAM such that:
– iff such that , and
– stops within steps on every input .
We also define
Note that the running time of is a function of , not . This difference is inconsequential for NP, since the composition of two powers is another power. But it is important for a more fine-grained analysis. We refer to a RAM machine as in Definition 5.1 as a nondeterministic machine, and to the in as the nondeterministic choices, or guesses, of the machine on input .
We can also define NTime in a way that is similar to BPTime, Definition 2.7. The two definitions are essentially equivalent. Our choice for BPTime is motivated by the identification of BPTime with computation that is actually run. For example, in a programming language one uses an instruction like Rand to obtain random values; one does not think of the randomness as being part of the input. By contrast, NTime is a more abstract model, and the definition with the nondeterministic guesses explicitly laid out is closer in spirit to a 3CNF.
All the problems we studied in section º4.3 are in .
Proof. For a 3Sat instance , the variables correspond to an assignment. Checking if the assignment satisfies is in P. This shows that 3Sat is in NP. QED
Exercise 5.2. Finish the proof by ad
dressing the other problems in Fact 5.1
How to think of NP
We can think of as the problems which admit a solution that can be verified efficiently, namely in . For example for 3Sat it is easy to verify if an assignment satisfies the clauses, for 3Color it is easy to verify if a coloring is such that any edge has endpoints of different colors, for SubsetSum it is easy to verify if a subset has a sum equal to a target, and so on. However, as we saw above this verification step can be cast in a restricted model, namely a 3CNF. So we don’t have to think of the verification step as using the full power of computation.
Here’s a vivid illustration of NP. Suppose I claim that the following matrix contains a :
How can you tell, without tediously examining the whole matrix? However, if I tell you that it’s in row 10, 8 digits from the right, you can quickly check that I am right. I won’t be able to cheat, since you can check my claims. On the other hand I can provide a proof that’s easy to verify.
P vs. NP
The flagship question of complexity theory is whether or not. This is a young, prominent special case of the grand challenge we introduced in Chapter 3. Contrary to the analogous question for , cf. section 2.5.2, the general belief seems to be that . Similarly to BPP, cf. Theorem 2.9, the best deterministic simulation of runs in exponential time by trying all nondeterministic guesses. This gives the middle inclusion in the following fact; the other two are by definition.
A consequence of the Time Hierarchy Theorem 3.4 is that . From the inclusions above it follows that
Thus, we are not completely clueless, and we know that at least one important separation is lurking somewhere. Most people appear to think that both separations hold, but we are unable to prove either.
For multi-tape machines, a separation between deterministic and non-deterministic linear time is in [24, 27].
We now go back to the question at the beginning of this chapter about reducing arbitrary computation to 3Sat. We shall reduce all of NP to 3Sat in Theorem 5.2. Problems like 3Sat admitting such reductions deserve a definition.
Definition 5.2. We call a problem :
NP-hard if every problem in reduces to in ;
NP-complete if it is NP-hard and in NP.
One can define -hard (and hence NP-complete) w.r.t. different reductions, cf. Chapter 4, and we will do so later. But the simple choice above suffices for now.
Complete problems are the “hardest problems” in the class, as formalized in the following fact.
Proof. This is because .
( Let . Because is NP-hard we know that QED
Fact 5.3 points to an important interplay between problems and complexity classes. We can study complexity classes by studying their complete problems, and vice versa.
The central result in the theory of NP completeness is the following.
Proof. 3Sat is in by Fact 5.1. Next we prove NP-hardness. The main idea is Theorem 5.1, while the rest of the proof mostly amounts to opening up definitions and using some previous simulations. Let and let be the corresponding TM which runs in time on inputs where and , for some constant . We can work with TMs instead of RAMs since they are equivalent up to a power loss, as we saw in Theorem 2.6. We can construct in a circuit of size such that for any we have by Theorem 2.4.
Now, suppose we are given an input for which we are trying to decide membership in . This is equivalent to deciding if by what we just said. We can “hard-wire” into to obtain the circuit only on the variables , with no loss in size. Here by “hard-wise” se mean replacing the input gates with the bits of . Now we can apply Theorem 5.1 to this new circuit to produce a 3CNF on variables and new variables such that , for any . The size of and the number of variables is power in the size of the circuit.
We have obtained:
as desired. QED
In section º4.3 we reduced 3Sat to other problems which are also in NP by Fact 5.1. This implies that all these problems are NP-complete. Here we use that if problem reduces to in P, and reduces to , then also reduces to . This is because if then , and so .
It is important to note that there is nothing special about the existence of NP-complete problems. The following is a simple such problem that does not require any of the machinery in this section.
Exercise 5.3. Consider the problem, given a RAM , an input , and , where is written in unary, decide if there is such that . Prove that this is NP-complete.
What if is written in binary?
The interesting aspect of NP-complete problems such as 3Sat and those in Corollary 5.1 is that they are very simple and structured, and don’t refer to computational models. This makes them suitable for reductions, and for inferring properties of the complexity class which are not evident from a machine-based definition.
5.3 From RAM to 3SAT in quasi-linear time
The framework in the previous section is useful to relate membership in P of different problems in NP, but it is not suitable for a more fine-grained analysis. For example, under the assumption that 3Sat is in we cannot immediately conclude that other problems in NP are solvable in this time or in about this time. We can only conclude that they are in . In particular, the complexity of 3Sat cannot be related to that of other central conjectures, such as whether 3Sum is in subquadratic time, Conjecture 4.1.
The culprit is the power loss in reducing RAM computation to circuits, mentioned at the beginning of the chapter. We now remedy this situation and present a quasi-linear reduction. As we did before, cf. Theorem 5.1 and Theorem 5.2, we first state a version of the simulation for (deterministic) computation which contains all the main ideas, and then we note that a completeness result follows.
Theorem 5.3. Given an input length , a time bound , and a RAM that runs in time on inputs of bits, we can compute in time a 3CNF on variables where such that for every :
We now present the proof of this amazing result; you may want to refer back to Definition 2.5 of a RAM. A key concept in the proof is the following “snapshot” of the RAM computation.
Definition 5.3. The internal configuration, abbreviated IC, of a RAM specifies:
- its registers,
- the program counter,
- the word length , and
- if the current instruction is a Read or Write then the IC includes the content of the memory cell indexed by .
Note that at most one memory cell is included in one IC. By contrast, the configuration of a TM (Definition 2.1) includes all its tape cells. Also note that an IC has length bits, where the is for the program counter, and the is for the rest, using that the maximum word length of a machine running in time is .
The key idea in the proof. At the high level, the approach is, like in Theorem 5.1, to guess computation and check it efficiently. We are going to guess the sequence of ICs, and we need additional ideas to check them efficiently by a circuit. This is not immediate, since, again, the RAM can use direct access to read and write in memory at arbitrary locations, something which is not easy to do with a circuit.
The key idea is to check operations involving memory independently from the operations involving registers but not memory. If both checks pass, then the computation is correct. More precisely, a sequence of internal configurations corresponds to the computation of the RAM on input iff for every :
- If does not access memory, then has its registers, program counter, and word length updated according to the instruction executed in ,
- If is computing a read operation then in register contains the most recent value written in memory cell . In case this cell was never written, then should contain if , if , and otherwise. The program counter in also points to the next instruction.
Rather than directly constructing a 3CNF that implements these checks, we construct a circuit and then appeal to Theorem 5.1. It is easy to construct a circuit of quasi-linear size implementing Check 1, since the circuit only has to check adjacent pairs of ICs. As remarked before, these ICs have length . For fixed Check 1 can be implemented by a circuit which depends on the RAM and has size power in the length of an IC. Taking an And of these circuits over the choices of gives a circuit of the desired size for Check 1.
The difficulty lies in Check 2, because the circuit needs to find “the most recent value written.” The solution is to sort the ICs by memory addresses. After sorting, we can implement Check (2) as easily as Check (1), since we just need to check adjacent pairs of ICs.
The emergence of sorting in the theory of NP-completeness cements the pivotal role this operation plays in computer science.
To implement this idea we need to be able to sort with a quasi-linear size circuit. Standard sorting algorithms like Mergesort, Heapsort, or Radixsort run in quasi-linear time on a RAM, but rely on direct addressing (cf. section º2.4) and for this reason cannot be easily implemented by a circuit of quasi-linear size. However other algorithms have been developed that do have such an implementation, for example a variant of Mergesort called Odd-Even-Mergesort , see also . This gives the following lemma.
We summarize the key steps in the proof.
Proof of Theorem 5.3. We construct a circuit and then appeal to Theorem 5.1. The extra variables correspond to ICs . An IC takes bits to specify, so we need variables . The circuit first performs Check (1) above for each adjacent pair of ICs. This takes size for each pair, and so size overall.
Then sorts the ICs by memory addresses, producing sorted ICs . This takes size by Lemma 5.1, using that the memory addresses have bits. Then the circuit performs Check (2) for each adjacent pair of ICs. The circuit size required for this is no more than for Check (1).
Finally, the circuit takes an And of the results of the two checks, and also checks that is accepting. QED
We can now prove completeness in a manner similar to Theorem 5.2, with a relatively simple extension of Theorem 5.3.
Theorem 5.4. Every problem in map reduces to 3Sat in , for every function such that is computable in time given .
The assumption on is similar to that in the hierarchy Theorem 3.4, and is satisfied by all standard functions including all those in this book – cf. discussion after Theorem 3.4.
Proof. Let be a RAM computing in the assumed time. Given an input of length we have to efficiently compute a 3CNF such that
First we compute , using the assumption. We now apply Theorem 5.3, but on a new input length , to accommodate for inputs of the form . This produces a formula of size in variables and new variables . We can now set to and conclude the proof. QED
With these sharper results we can now study hardness and completenss within time bounds such as , etc. We work out an example in the next section.
5.3.1 Quasilinear-time completeness
In this section we use the machinery we just developed to study completeness in quasi-linear time, instead of power time.
Theorem 5.5. 3Sat is complete for QLin-NTime with respect to mapping reductions in QLin-Time. That is:
– 3Sat is in QLin-NTime, and
– every problem in QLin-NTime map reduces to 3Sat in QLin-Time.
Proof. To show that 3Sat is in QLin-NTime, consider a 3CNF instance of length . This instance has at most variables, and we can guess an assignment to them within our budget of non-deterministic guesses. There remains to verify that satisfies . For this, we can do one pass over the clauses. For each clause, we access the bits in corresponding to the 3 variables in the clause, and check if the clause is satisfied. This takes constant time per clause, and so time overall.
The second part follows from Theorem 5.4, using the fact that the composition of two quasilinear functions is also quasilinear (similarly to the fact that the composition of two power functions is also a power). QED
Note that the proof that 3Sat is in QLin-NTime relies on our computational model being a RAM, because we use direct access to fetch the values for the variables in a clause.
We can now give the following quasi-linear version of Fact 5.3. The only extra observation for the proof is again that the composition of two quasi-linear functions is quasi-linear.
Exercise 5.4. Prove that Theorem 5.5 holds with 3Color instead of 3Sat. What about Clique and Subset-sum?
Exercise 5.5. Prove that 3Sum reduces to 3Sat in Subquadratic time. That is: Conjecture 4.1 is false).
5.4 Completeness in other classes
The completeness phenomenon is not special to NP but enjoyed by many other classes. In this section we begin to explore completeness for NExp and Exp. One needs to be careful how hardness (and hence completeness) is defined, since these classes are known to be different from by the hierarchy Theorem 3.4. So defining a problem to be NExp-hard if would mean simply that . To avoid this in this section hardness (hence completeness) is defined w.r.t. mapping reductions, cf. Chapter 4. (Another option would be to replace with say , since it is not known if .)
5.4.1 NExp completeness
Complete problems for NExp include succinct versions of problems complete for NExp. Here succinct means that rather than giving the input to the problem in standard format, the input consists instead of a circuit encoding , for example equals bit of , for every .
Definition 5.5. The Succinct-3Sat problem: Given a circuit encoding a 3CNF , does have a satisfying assignment?
Proof sketch.. Let us first show that Succinct-3Sat is in NExp. Given a circuit of length , we can run it on every possible input (of length ) and write down the formula encoded by . This formula has size . We can then use the fact that 3Sat is in NP to decide satisfiability of this formula in non-deterministic power time in , that is .
To prove NExp hardness it is convenient to work with TMs rather than RAMs. The main observation is that in the simulation of a TM on an input by a circuit , Theorem 2.4, the circuit is very regular, in the sense that we can construct another circuit which is a succinct encoding of . The circuit is given as input indexes to gates in and outputs the type of the gate and its wires. The size of is power in the index length and . Thus, if has size , only needs size . If , has size power in , as desired. The transformation from circuit to 3CNF in Theorem 5.1 is also regular and can be done succinctly. QED
As a consequence, we obtain the following “concrete” problem not in .
Exp-complete problems include several two-player games. The important feature for completeness is that the game may last for an exponential number of steps (otherwise it would belong to a class believed to be stricter which we will investigate in Chapter ??). These games include (generalized versions of) Chess  and Checkers .
5.5 Power from completeness
The realization that arbitrary computation can be reduced to 3Sat and other problems is powerful and liberating. In particular it allows us to significantly widen the net of reductions.
5.5.1 Optimization problems
As observed in section º4.6, 3Sat trivially reduces to Max-3Sat. The converse will be shown next.
Proof. Consider the problem Atleast-3Sat: Given a 3CNF formula and an integer , is there an assignment that satisfies at least clauses? This is in and so can be reduced to 3Sat in . This is the step that’s not easy without “thinking completeness:” given an algorithm for 3Sat it isn’t clear how to use it directly to solve Atleast-3Sat.
Hence, if 3Sat is in P so is Atleast-3Sat. On input a 3CNF , using binary search and the fact that Atleast-3Sat is in P, we can find in P the largest s.t. . Having found this , there remains to construct an assignment satisfying the clauses. This can be done fixing one variable at the time as in Theorem 4.5. QED
5.5.2 NP is as easy as detecting unique solutions
A satisfiable 3CNF can have multiple satisfying assignments. On the other hand some problems and puzzles have unique solutions. In this section we relate these two scenarios.
Definition 5.6. Unique-CktSat is the problem: Given a circuit s.t. there is at most one input for which , decide if such an input exists.
Unique-3Sat is the Unique-CktSat problem restricted to 3CNF circuits.
Theorem 5.8.  3Sat reduces to Unique-3Sat in BPP.
We in fact reduce 3Sat to Unique-CktSat. Then Unique-CktSat can be reduced to Unique-3Sat observing that the reduction in Theorem 5.1 preserves uniqueness.
The beautiful proof uses a powerful and general technique in randomized computation: pairwise uniformity, sometimes more generically referred to as hashing. We first define such functions and give efficient constructions. Then we show how to use them to “isolate” assignments.
Definition 5.7. A distribution on functions mapping is called pairwise uniform if for every and one has
This is saying that on every pair of inputs is behaving as a completely uniform function. Yet unlike completely uniform functions, the next lemma shows that pairwise uniform functions can have a short description, which makes them suitable for use in algorithms.
Exercise 5.6. Let be a finite field. Define the random function as where are uniform in .
Prove that is pairwise uniform.
Explain how to use to obtain a pairwise uniform function from to for any given .
Exercise 5.7. Define the random function as where is uniform in and is uniform in .
Prove that is pairwise uniform.
Explain how to use to obtain a pairwise uniform function from to for any given .
We can now state the lemma that we use to isolate assignments.
Lemma 5.2. Let be a pairwise uniform function mapping , and let . The probability that there is a unique element such that is
In particular, if this prob. is .
Proof. For fixed , the probability is the unique element mapped to is at least the prob. that is mapped to minus the prob. that both and some other are mapped to . This is
These events for different are disjoint; so the target probability is at least the sum of the above over . QED
Proof of Theorem 5.8. Given a 3Sat instance with variables , we pick a random from to . We then pick a pairwise uniform function mapping to , and consider the circuit
This circuit has size .
If is not satisfiable, is not satisfiable, for any random choices.
Now suppose that has satisfying assignment. With prob. we will have , in which case Lemma 5.2 guarantees that has a unique satisfying assignment with prob. .
Overall, has a unique satisfying assignment with prob. . Hence the Unique-3Sat algorithm on outputs with prob. . If we repeat this process times, with independent random choices, the Or of the outcomes gives the correct answer with prob. . QED
Problem 5.1. In Theorem 4.5 we reduced Search-3Sat to 3Sat.
– Suppose 3Sat is computable by circuits of depth . What would be the depth of the circuits for Search-3Sat given by the reduction?
– Reduce Search-3Sat to 3Sat in .
Hint: First work with randomized circuits. Use ideas in proof of Theorem 4.5.
 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.
 Leonard Adleman. Two theorems on random polynomial time. In 19th IEEE Symp. on Foundations of Computer Science (FOCS), pages 75–83. 1978.
 Dana Angluin and Leslie G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. J. Comput. Syst. Sci., 18(2):155–193, 1979.
 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.
 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.
 Kenneth E. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Computing Conference, volume 32, pages 307–314, 1968.
 Stephen A. Cook. A hierarchy for nondeterministic time complexity. J. of Computer and System Sciences, 7(4):343–353, 1973.
 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.
 Anka Gajentaan and Mark H. Overmars. On a class of problems in computational geometry. Comput. Geom., 5:165–185, 1995.
 M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
 K. G÷del. ▄ber formal unentscheidbare sΣtze der Principia Mathematica und verwandter systeme I. Monatsh. Math. Phys., 38, 1931.
 Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.
 David Harvey and Joris van der Hoeven. Integer multiplication in time . Annals of Mathematics, 193(2):563 – 617, 2021.
 F. C. Hennie. One-tape, off-line turing machine computations. Information and Control, 8(6):553–578, 1965.
 Fred Hennie and Richard Stearns. Two-tape simulation of multitape turing machines. J. of the ACM, 13:533–546, October 1966.
 Russell Impagliazzo and Ramamohan Paturi. The complexity of -sat. In IEEE Conf. on Computational Complexity (CCC), pages 237–, 1999.
 Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Computer & Systems Sciences, 63(4):512–530, Dec 2001.
 Russell Impagliazzo and Avi Wigderson. if requires exponential circuits: Derandomizing the XOR lemma. In 29th ACM Symp. on the Theory of Computing (STOC), pages 220–229. ACM, 1997.
 Kojiro Kobayashi. On the structure of one-tape nondeterministic turing machine time hierarchy. Theor. Comput. Sci., 40:175–193, 1985.
 Leonid A. Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):115–116, 1973.
 O. B. Lupanov. A method of circuit synthesis. Izv. VUZ Radiofiz., 1:120–140, 1958.
 NEU. From RAM to SAT. Available at http://www.ccs.neu.edu/home/viola/, 2012.
 Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3):425–440, 1991.
 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.
 Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. of the ACM, 26(2):361–381, 1979.
 J. M. Robson. N by N checkers is exptime complete. SIAM J. Comput., 13(2):252–267, 1984.
 Rahul Santhanam. On separators, segregators and time versus space. In IEEE Conf. on Computational Complexity (CCC), pages 286–294, 2001.
 Arnold Sch÷nhage. Storage modification machines. SIAM J. Comput., 9(3):490–508, 1980.
 Claude E. Shannon. The synthesis of two-terminal switching circuits. Bell System Tech. J., 28:59–98, 1949.
 Victor Shoup. New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54(189):435–447, 1990.
 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.
 Alan M. Turing. On computable numbers, with an application to the entscheidungsproblem. Proc. London Math. Soc., s2-42(1):230–265, 1937.
 Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theor. Comput. Sci., 47(3):85–93, 1986.
 Emanuele Viola. Reducing 3XOR to listing triangles, an exposition. Available at http://www.ccs.neu.edu/home/viola/, 2011.
 Emanuele Viola. Pseudorandom bits and lower bounds for randomized turing machines. Theory of Computing, 18(10):1–12, 2022.