Mathematics of the impossible: Computational Complexity, Chapter 5, Completeness: Reducing arbitrary computation

Thoughts 2023-02-24

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 $C:\{0,1\} ^{n}\to \{0,1\}$ with $s$ gates we can compute in $\text {P}$ a 3CNF formula $f_{C}$ in $n+s$ variables such that for every $x\in \{0,1\} ^{n}$ :

$\begin{aligned} C(x)=1\Leftrightarrow \exists y\in \{0,1\} ^{s}:f_{C}(x,y)=1. \end{aligned}$

The key idea to guess computation and check it efficiently, using that computation is local. The additional $s$ variables one introduces contain the values of the gates during the computation of $C$ on $x$ . 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 $y_{i}$ for each non-input gate $g_{i}$ in $C$ . The value of $y_{i}$ is intended to be the value of gate $g_{i}$ during the computation. Whether the value of a gate $g_{i}$ is correct is a function of $3$ variables: $y_{i}$ and the $\le 2$ gates that input $g_{i}$ , 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 $y_{o}$ for the output gate $g_{o}$ . 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 $c\log s$ , 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 $t$ to 3Sat of size $t\log ^{c}t$ . 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 $t$ to 3CNFs of size $t^{c}$ . 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 $\exists$ 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 $C(x,y)$ has two inputs, $x$ and $y$ . We can think of it as a non-deterministic circuit, which on input $x$ outputs $1$ iff $\exists y:C(x,y)$ . 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 $\exists$ 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 $(t(n))$ is the set of functions $f:X\subseteq \{0,1\}^* \to \{0,1\}$ for which there is a RAM $M$ such that:

– $f(x)=1$ iff $\exists y\in \{0,1\} ^{t(|x|)}$ such that $M(x,y)=1$ , and

– $M(x,y)$ stops within $t(|x|)$ steps on every input $(x,y)$ .

We also define

$\begin{aligned} \text {NP}:= & \bigcup _{d\ge 1}\text {NTime}(n^{d}),\\ \text {NExp}:= & \bigcup _{d\ge 1}\text {NTime}(2^{n^{d}}). \end{aligned}$

Note that the running time of $M$ is a function of $|x|$ , not $|(x,y)|$ . 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 $y$ in $M(x,y)$ as the nondeterministic choices, or guesses, of the machine on input $x$ .

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 $\text {NP}$ .

Fact 5.1. 3Sat, Clique, Cover-by-vertexes, SubsetSum, and 3Color are in $\text {NP}$ .

Proof. For a 3Sat instance $f$ , the variables $y$ correspond to an assignment. Checking if the assignment satisfies $f$ 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 $\text {NP}$ as the problems which admit a solution that can be verified efficiently, namely in $\text {P}$ . 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 $\text {P}$ computation.

Here’s a vivid illustration of NP. Suppose I claim that the following matrix contains a $9$ :

56788565634705634705637480563476

70156137805167840132838202386421

85720582340570372307580234576423

80275880237505788075075802346518

78502378564067807582348057285428

05723748754543650350562378804337

52305723485008160234723884077764

86543234567865435674567836738063

45463788486754345743457483460040

73273873486574375464584895741832

85075783485634856237847287422112

83748874883753485745788788223201

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 $\text {P}=\text {NP}$ or not. This is a young, prominent special case of the grand challenge we introduced in Chapter 3. Contrary to the analogous question for $\text {BPP}$ , cf. section 2.5.2, the general belief seems to be that $\text {P}\ne \text {NP}$ . Similarly to BPP, cf. Theorem 2.9, the best deterministic simulation of $\text {NP}$ runs in exponential time by trying all nondeterministic guesses. This gives the middle inclusion in the following fact; the other two are by definition.

Fact 5.2. $\text {P}\subseteq \text {NP}\subseteq \text {Exp \ensuremath {\subseteq \text {NExp}}}$ .

A consequence of the Time Hierarchy Theorem 3.4 is that $\text {P}\ne \text {Exp}$ . From the inclusions above it follows that

$\begin{aligned} \text {P}\ne \text {NP}\text { or NP}\ne \text {Exp, possibly both}. \end{aligned}$

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

5.2 NP-completeness

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 $L$ :

NP-hard if every problem in $\text {NP}$ reduces to $L$ in $\text {P}$ ;

NP-complete if it is NP-hard and in NP.

One can define $\text {NP}$ -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.

Fact 5.3. Suppose $\text {L}$ is NP-complete. Then $L\in \text {P}\Leftrightarrow \text {P}=\text {NP}$ .

Proof. $(\Leftarrow )$ This is because $L\in \text {NP}$ .

( $\Rightarrow )$ Let $L'\in \text {NP}$ . Because $L$ is NP-hard we know that $L\in \text {P\ensuremath {\Rightarrow L'\in \text {P}}.}$ 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.

Theorem 5.2. [7, 20] 3Sat is NP-complete.

Proof. 3Sat is in $\text {NP}$ 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 $L\in \text {NP}$ and let $M$ be the corresponding TM which runs in time $n^{d}$ on inputs $(x,y)$ where $|x|=n$ and $|y|=n^{d}$ , for some constant $d$ . 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 $\text {P }$ a circuit $C(x,y)$ of size $c_{M}n^{c_{d}}$ such that for any $x,y$ we have $M(x,y)=1\Leftrightarrow C(x,y)=1$ by Theorem 2.4.

Now, suppose we are given an input $w$ for which we are trying to decide membership in $L$ . This is equivalent to deciding if $\exists y:C(w,y)=1$ by what we just said. We can “hard-wire” $w$ into $C$ to obtain the circuit $C_{w}(y):=C(w,y)$ only on the variables $y$ , with no loss in size. Here by “hard-wise” se mean replacing the input gates $x$ with the bits of $w$ . Now we can apply Theorem 5.1 to this new circuit to produce a 3CNF $f_{w}$ on variables $y$ and new variables $z$ such that $C_{w}(y)=1\Leftrightarrow \exists z:f(y,z)=1$ , for any $y$ . The size of $f_{w}$ and the number of variables $z$ is power in the size of the circuit.

We have obtained:

$\begin{aligned} w\in L\Leftrightarrow \exists y:M(w,y)=1\Leftrightarrow \exists y:C_{w}(y)=1\Leftrightarrow \exists y,z:f_{w}(y,z)=1\Leftrightarrow f_{w}\in \text {3Sat,} \end{aligned}$

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 $A$ reduces to $B$ in P, and $B$ reduces to $C$ , then also $A$ reduces to $C$ . This is because if $C\in \text {P}$ then $B\in \text {P}$ , and so $A\in \text {P}$ .

Corollary 5.1. Clique, Cover-by-vertexes, Subset-sum, and 3Color are NP-complete.

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 $M$ , an input $x$ , and $t\in \mathbb {N}$ , where $t$ is written in unary, decide if there is $y\in \{0,1\} ^{t}$ such that $M(x,y)=1$ . Prove that this is NP-complete.

What if $t$ 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 $\text {Time}(cn)$ 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 $\text {P}$ . 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 $n\in \mathbb {N}$ , a time bound $t\in \mathbb {N}$ , and a RAM $M$ that runs in time $t$ on inputs of $n$ bits, we can compute in time $t':=c_{M}t(\log t)^{c}$ a 3CNF $f$ on variables $(x,y)$ where $|y|\le t'$ such that for every $x\in \{0,1\} ^{n}$ :

$\begin{aligned} M(x)=1\iff \exists y:f(x,y)=1. \end{aligned}$

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 $w$ , and
if the current instruction is a Read $r_{i}:=\mu [r_{j}]$ or Write $\mu [r_{j}]:=r_{i}$ then the IC includes the content $\mu [r_{j}]$ of the memory cell indexed by $r_{j}$ .

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 $\le c_{M}+c\log t$ bits, where the $c_{M}$ is for the program counter, and the $c\log t$ is for the rest, using that the maximum word length of a machine running in time $t\ge n$ is $c\log t$ .

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 $s_{1},s_{2},\ldots ,s_{t}$ corresponds to the computation of the RAM on input $x$ iff for every $i<t$ :

If $s_{i}$ does not access memory, then $s_{i+1}$ has its registers, program counter, and word length updated according to the instruction executed in $s_{i}$ ,
If $s_{i}$ is computing a read operation $r_{i}:=\text {\ensuremath {\mu [r_{j}]}}$ then in $s_{i+1}$ register $r_{j}$ contains the most recent value written in memory cell $r_{j}$ . In case this cell was never written, then $r_{j}$ should contain $x_{j}$ if $j\in \{1,2,\ldots ,n\}$ , $n$ if $j=0$ , and $0$ otherwise. The program counter in $s_{i+1}$ 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 $\le c_{M}+c\log t$ . For fixed $i,$ 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 $i$ 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 [6], see also [22]. This gives the following lemma.

Lemma 5.1. Given $t$ and $m$ we can compute in time $t':=t\cdot (m\log t)^{c}$ a circuit (of size $\le t'$ ) that sorts $t$ integers of $m$ bits.

We summarize the key steps in the proof.

Proof of Theorem 5.3. We construct a circuit $C_{M}$ and then appeal to Theorem 5.1. The extra variables $y$ correspond to $t$ ICs $s_{1},s_{2},\ldots ,s_{t}$ . An IC takes $c_{M}+c\log t$ bits to specify, so we need $\le c_{M}t\log t$ variables $y$ . The circuit $C_{M}$ first performs Check (1) above for each adjacent pair $(s_{i},s_{i+1})$ of ICs. This takes size $c_{M}\log ^{c}t$ for each pair, and so size $c_{M}t\log ^{c}t$ overall.

Then $C_{M}$ sorts the ICs by memory addresses, producing sorted ICs $s'_{1},s'_{2},\ldots ,s'_{t}$ . This takes size $t\cdot \log ^{c}t$ by Lemma 5.1, using that the memory addresses have $\le c\log t$ bits. Then the circuit performs Check (2) for each adjacent pair $(s'_{i},s'_{i+1})$ 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 $s_{t}$ 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 $L$ in $\text {NTime}(t)$ map reduces to 3Sat in $\text {Time}(c_{L,t}t\log ^{c}t)$ , for every function $t\ge n$ such that $t(x)$ is computable in time $t(x)$ given $x$ .

The assumption on $t$ 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 $M$ be a RAM computing $L$ in the assumed time. Given an input $w$ of length $n$ we have to efficiently compute a 3CNF $f$ such that

$\begin{aligned} \exists y\in \{0,1\} ^{t(n)}:M(w,y)=1\iff \exists y\in \{0,1\} ^{c_{L,t}t(n)\log ^{c}t(n)}:f(y)=1. \end{aligned}$

First we compute $t(n)$ , using the assumption. We now apply Theorem 5.3, but on a new input length $n':=c(n+t)\le ct$ , to accommodate for inputs of the form $(x,y)$ . This produces a formula $f$ of size $c_{L,t}t(\log t)^{c}$ in variables $(x,y)$ and new variables $z$ . We can now set $x$ to $w$ and conclude the proof. QED

With these sharper results we can now study hardness and completenss within time bounds such as $n^{2}$ , $n\log ^{3}n$ 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.

Definition 5.4. We define the quasi-linear time complexity classes

$\begin{aligned} \text {QLin-Time}:= & \bigcup _{d\in \mathbb {N}}\text {Time}(n\log ^{d}n)\text { and}\\ \text {QLin-NTime}:= & \bigcup _{d\in \mathbb {N}}\text {NTime}(n\log ^{d}n). \end{aligned}$

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 $f$ of length $n$ . This instance has at most $n$ variables, and we can guess an assignment $y$ to them within our budget of non-deterministic guesses. There remains to verify that $y$ satisfies $f$ . For this, we can do one pass over the clauses. For each clause, we access the bits in $y$ corresponding to the 3 variables in the clause, and check if the clause is satisfied. This takes constant time per clause, and so time $cn$ 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.

Corollary 5.2. $\text {3Sat}\in \text {QLin-NTime}\Leftrightarrow \text {QLin-NTime}=\text {QLin-Time.}$

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: $\text {3Sat}\in \text {SubquadraticTime\ensuremath {\Rightarrow \text {3Sum}\in \text {SubquadraticTime}} (i.e., }$ 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 $\text {P}$ by the hierarchy Theorem 3.4. So defining a problem $L$ to be NExp-hard if $L\in \text {P}\Rightarrow \text {NExp}=\text {P}$ would mean simply that $L\not \in \text {P}$ . 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 $\text {P}$ with say $\text {BPP}$ , since it is not known if $\text {BPP}=\text {NExp}$ .)

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 $x$ to the problem in standard format, the input consists instead of a circuit $C:\{0,1\} ^{m}\to \{0,1\}$ encoding $x$ , for example $C(i)$ equals bit $i$ of $x$ , for every $i$ .

Definition 5.5. The Succinct-3Sat problem: Given a circuit $C$ encoding a 3CNF $f_{C}$ , does $f_{C}$ have a satisfying assignment?

Theorem 5.6. Succinct-3Sat is NExp complete with respect to power-time mapping reductions.

Proof sketch.. Let us first show that Succinct-3Sat is in NExp. Given a circuit $C$ of length $n$ , we can run it on every possible input (of length $\le n$ ) and write down the formula $f_{C}$ encoded by $C$ . This formula has size $\le 2^{n}$ . We can then use the fact that 3Sat is in NP to decide satisfiability of this formula in non-deterministic power time in $2^{n}$ , that is $\text {NTime}(2^{cn})\subseteq \text {NExp}$ .

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 $M$ on an input $x$ by a circuit $C_{M}$ , Theorem 2.4, the circuit is very regular, in the sense that we can construct another circuit $S_{M}$ which is a succinct encoding of $C_{M}$ . The circuit $S_{M}$ is given as input indexes to gates in $C_{M}$ and outputs the type of the gate and its wires. The size of $S_{M}$ is power in the index length and $M$ . Thus, if $C_{M}$ has size $t^{c}$ , $S_{M}$ only needs size $\log ^{c}t$ . If $t=2^{n^{d}}$ , $S_{M}$ has size power in $n$ , 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 $\text {P}$ .

Corollary 5.3. $\text {Succinct-3Sat}\not \in \text {P}$ .

5.4.2 Exp-completeness

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 [8] and Checkers [26].

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.

Theorem 5.7. Max-3Sat reduces to 3Sat in $\text {P}$ .

Proof. Consider the problem Atleast-3Sat: Given a 3CNF formula and an integer $t$ , is there an assignment that satisfies at least $t$ clauses? This is in $\text {NP}$ and so can be reduced to 3Sat in $\text {P}$ . 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 $f$ , using binary search and the fact that Atleast-3Sat is in P, we can find in P the largest $t$ s.t. $(f,t)\in \text {Atleast-3Sat}$ . Having found this $t$ , 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 $C$ s.t. there is at most one input $x$ for which $C(x)=1$ , decide if such an input exists.

Unique-3Sat is the Unique-CktSat problem restricted to 3CNF circuits.

Theorem 5.8. [33] 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 $H$ on functions mapping $S\to T$ is called pairwise uniform if for every $x,x'\in S$ and $y,y'\in T$ one has

$\begin{aligned} \mathbb {P}_{H}[H(x)=y\wedge H(x')=y']=1/|T|^{2}. \end{aligned}$

This is saying that on every pair of inputs $H$ 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 $\mathbb {F}_{q}$ be a finite field. Define the random function $H:\mathbb {F}_{q}\to \mathbb {F}_{q}$ as $H(x):=Ax+B$ where $A,B$ are uniform in $\mathbb {F}_{q}$ .

Prove that $H$ is pairwise uniform.

Explain how to use $H$ to obtain a pairwise uniform function from $\{0,1\} ^{n}$ to $\{0,1\} ^{t}$ for any given $t\le n$ .

Exercise 5.7. Define the random function $H_{1}:\{0,1\} ^{n}\to \{0,1\}$ as $H(x):=\sum _{i\le n}A_{i}x_{i}+B$ where $A$ is uniform in $\{0,1\} ^{n}$ and $B$ is uniform in $\{0,1\}$ .

Prove that $H_{1}$ is pairwise uniform.

Explain how to use $H$ to obtain a pairwise uniform function from $\{0,1\} ^{n}$ to $\{0,1\} ^{t}$ for any given $t\le n$ .

We can now state the lemma that we use to isolate assignments.

Lemma 5.2. Let $H$ be a pairwise uniform function mapping $S\to T$ , and let $1\in T$ . The probability that there is a unique element $s\in S$ such that $H(s)=1$ is

$\begin{aligned} \ge \frac {|S|}{|T|}-\frac {|S|^{2}}{|T|^{2}}. \end{aligned}$

In particular, if $|T|/8\le |S|\le |T|/4$ this prob. is $\ge \frac {1}{8}-\frac {1}{16}\ge 1/8$ .

Proof. For fixed $s\in S$ , the probability $s$ is the unique element mapped to $1$ is at least the prob. that $s$ is mapped to $1$ minus the prob. that both $s$ and some other $s'\ne s$ are mapped to $1$ . This is

$\begin{aligned} \ge \frac {1}{|T|}-\frac {|S|-1}{|T|^{2}}. \end{aligned}$

These events for different $s\in S$ are disjoint; so the target probability is at least the sum of the above over $s\in S$ . QED

Proof of Theorem 5.8. Given a 3Sat instance $\phi$ with $\le n$ variables $x$ , we pick a random $i$ from $0$ to $n+c$ . We then pick a pairwise uniform function mapping $\{0,1\} ^{n}$ to $\{0,1\} ^{i}$ , and consider the circuit

$\begin{aligned} C:=\phi (x)\wedge H(x)=0^{i}. \end{aligned}$

This circuit has size $n^{c}$ .

If $\phi$ is not satisfiable, $C$ is not satisfiable, for any random choices.

Now suppose that $\phi$ has $s\ge 1$ satisfying assignment. With prob. $\ge 1/n$ we will have $2^{i-3}\le s\le 2^{i-2}$ , in which case Lemma 5.2 guarantees that $C$ has a unique satisfying assignment with prob. $\ge c$ .

Overall, $C$ has a unique satisfying assignment with prob. $\ge c/n$ . Hence the Unique-3Sat algorithm on $C$ outputs $1$ with prob. $\ge c/n$ . If we repeat this process $cn$ times, with independent random choices, the Or of the outcomes gives the correct answer with prob. $\ge 2/3$ . QED

5.6 Problems

Problem 5.1. In Theorem 4.5 we reduced Search-3Sat to 3Sat.

– Suppose 3Sat is computable by circuits of depth $c\log n$ . What would be the depth of the circuits for Search-3Sat given by the reduction?

– Reduce Search-3Sat to 3Sat in $\text {\ensuremath {\bigcup _{a>0}}}\text {Depth}(a\log n)$ .

Hint: First work with randomized circuits. Use ideas in proof of Theorem 4.5.

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] Kenneth E. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Computing Conference, volume 32, pages 307–314, 1968.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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