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

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 .

Fact 5.1. 3Sat, Clique, Cover-by-vertexes, SubsetSum, and 3Color 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 :

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

Fact 5.2. .

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

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 :

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.

Fact 5.3. Suppose is NP-complete. Then .

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.

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

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 .

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 , 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 :

1. If does not access memory, then has its registers, program counter, and word length updated according to the instruction executed in ,
2. 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 [6], see also [22]. This gives the following lemma.

Lemma 5.1. Given and we can compute in time a circuit (of size ) that sorts integers of bits.

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.

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

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.

Corollary 5.2.

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?

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

Corollary 5.3. .

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 .

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

5.6 Problems

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.

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

Eric Allender’s day

is unfolding at Simons institute (and tomorrow is Valentine’s day, joke by Rahul).  The speakers are praising Eric’s many contributions to the field, so I thought I’d add my praise, since over the years I interacted with Eric in many different capacities, excluding coauthor, but there’s time to fix that, Eric.  I met him the first time 20 years ago in Denmark.  I had already read some of his surveys, and I remember being somewhat surprised that the mental image I had subconsciously created of him didn’t match the way he looked.  Turns out even he was expecting something different from the emails we had exchanged — pictures weren’t online back then.  Anyway, back to more scientific matters, I told him that his surveys were one of the first things I read, and I think he said it was good that they had had an effect.

Indeed, they have, his works and surveys have had a significant impact on my research.  Especially his surveys on low-level complexity classes, a topic dear to my heart.  Counting hierarchies, arithmetic circuits, and the division breakthroughs are some of the many things his surveys exposed me to.  Eric has a unique angle about these topics, and I often go back to his surveys and papers for knowledge and inspiration.  More in line with the topic of the workshop, people are emphasizing how Eric anticipated recent trends, such as “meta complexity,” before they were a thing.  Way to go.

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

---

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.

Contents

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 to a function is a way to compute given that we can compute . One can define reductions in different ways, depending on the overhead required to compute given that we can compute . The most general type of reduction is simply an implication.

General form of reduction from to :

  If can be computed with resources then can be computed with resources .

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

Definition 4.1. We say that reduces to in (or under reductions) if

A further special and noteworthy case is when , or ; in these cases the reduction can be interpreted as saying that if is easy to compute than is too.But in general may not be equal to . We will see examples of such implications for various and .

It is sometimes useful to be more specific about how the implication is proved. For example, this is useful when inferring various properties of from properties of , 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 map reduces to in (or via a map in ) if there is such that for every .

Exercise 4.1. Suppose that map reduces to in .

(1) Suppose . Show reduces to in .

(2) Suppose . Can you still show that reduces to in ?

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 -bit integers is in (Exercise 2.8). But the smallest circuit known for multiplication has gates [10]. (The same situation holds for MTMs; over RAMs and related models multiplication can be done in time [21].) It is a long-standing question whether we can multiply two -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

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 -bit integers. Squaring is the problem of computing the square of an -bit integer.

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

Proof. Suppose computes Squaring. Then we can multiply using equation (??). Specifically, given and we use Exercise 2.8 to compute and . (We haven’t seen subtraction or negative integers, but it’s similar to addition.) Then we run 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 problem: Given a list of integers, are there three integers that sum to ?

It is easy to solve 3Sum in time on a RAM. (We can first sort the integers then for each pair we can do a binary search to check if is also present.) The time can be improved .

3Sum is believed to require quadratic time.

Definition 4.5. .

Conjecture 4.1. .

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] Conjecture 4.1 is false).

Proof. We map instance of 3Sum to the points

and solve Collinearity on those points.

To verify correctness, notice that points and are on a line iff

Because , this condition is equivalent to

Assuming , i.e., that the 3Sum instance consists of distinct numbers, this is equivalent to , 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 , , and of numbers, are there s.t. 

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 where is the exponent of matrix multiplication. If then the bound is . It is not known if any subquadratic algorithm for 3Sum would improve these bounds. However, we can show that an improvement follows if for a small enough .

Theorem 4.3. [26] for any .

The reduction can be derandomized (that is, one can replace with in the conclusion) but the randomized case contains the main ideas.

Proof. We assign random numbers with bits to each node in the graph. The 3Sum instance consists of the integers for every edge in the graph.

To verify correctness, suppose that there is a cycle

in the graph. Then we have , for any random choices.

Conversely, suppose there is no cycle, and consider any three numbers from the reduction and its corresponding edges. Some node has unequal in-degree and out-degree in those edges. This means that when summing the three numbers, the random variable will not cancel out. When selecting uniform values for that variable, the probability of getting is at most .

By a union bound, the probability there there are three numbers that sum to zero is 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 . 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 , is there an assignment s.t. ?

Conjecture 4.2.

Stronger conjectures have been made.

Conjecture 4.3. [13] [Exponential time hypothesis (ETH)] There is such that there is no algorithm that on input a CNF with variables and clauses decides if is satisfiable in time .

Conjecture 4.4. [14] [Strong exponential-time hypothesis (SETH)] For every there is such that there is no algorithm that on input a CNF with variables and clauses decides if is satisfiable in time .

It is known that 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 , , 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,

Reduce 3Sat to System in .

Exercise 4.5. For an integer , -Color is the problem of deciding if the nodes of a given undirected graph can be colored using 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 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 , following these steps:

1. Given a graph , introduce variables representing that node has color , where ranges in the set of colors . Describe a set of clauses that is satisfiable if and only if for every there is exactly one such that 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 and of strings of the same length, determine if there is and such that the bit-wise Or equals the all-one vector.

The Or-Vector problem is in . We can show that a substantial improvement would disprove SETH.

Theorem 4.4.

Proof. Divide the variables in two blocks of each. For each assignment to the variables in the first block construct the vector in where bit is iff clause is satisfied by the variables in the first block. Call the resulting set of vectors. Let and note . Do the same for the other block and call the resulting set .

Note that is satisfiable iff such that .

Constructing these sets takes time . If for some , we can take 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 . That is: .

Proof. We construct a satisfying assignment one variable at the time. Given a satisfiable 3CNF, set the first variable to 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 and go to the next variable. QED

Exercise 4.7. Show .

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 such that on input any satisfiable formula :

(1) outputs a satisfying assignment, and

(2) If there is a RAM that on input outputs a satisfying assignment for in steps then stops in steps.

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

Proof. For the RAM simulates RAM for steps. 2.2 guarantees that for each the simulation takes time . If RAM stops and outputs , then checks in time if is a satisfying assignment. If it is, then outputs and stops. Otherwise it continues.

Now let be as in (2). As before, we work with an enumeration of programs where each program appears infinitely often. Hence we can assume that has a description of length . Thus the simulation will terminate when .

The time spent by for a fixed is . Hence he total running time of is

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 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. -Gap-3Sat is the 3Sat problem restricted to input formulas that are either satisfiable or such that any assignment satisfies at most a fraction of clauses.

Note that 3Sat is equivalent to -Gap-3Sat for , since a formula of size has at most clauses. At first sight it is unclear how to connect the problems when is much smaller. But in fact it is possible to obtain a constant . 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 such that .

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 -approximating Max-3Sat, that is, computing an assignment that satisfies a number of clauses that is at least a fraction of the maximum possible clauses that can be satisfied.

The PCP Theorem 4.7 implies that 3Sat reduces to approximating Max-3Sat, for some constant .

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

Exercise 4.8. Turn this latter observation in an efficient randomized algorithm with an approximation factor .

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 . (Hint: Consider the Padded-Palindromes problem which is like palindromes except the input is divided in blocks of 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 .

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 -local map (in particular, a circuit of constant depth).

Problem 4.5. Suppose there exists such that Theorem 4.6 holds with the running time of replaced with . (That is, the dependence on the program description improved to polynomial, and we allow even weaker dependence on .) Prove that .

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

Nathan Never strikes back

Amiga Germany Fan’zine – #5 features Nathan Never, 30 years after the game came out (the article is from some months ago, but I just found out). You can read the article here.

My first day of high school I was looking for a desk, and the one that was left was occupied by Marco Genovesi (also see previous post about Black Viper, our other game together, also featured in article). We had both programmed a little the mythical C64. I had written in basic a fighting game inspired by Hokuto No Ken. It was hand-coded pixellated sprites doing flying martial arts kicks. It was on a cassette — I didn’t have a floppy disk. I would love to see it again, but it seems lost forever. It was my first game, written sometime when I was between 10 and 12.

If I think back at my schools, from elementary to high, I scream in horror. There was nothing. No play-yard, no props, nothing. Even the walls! How much does it cost to hang a world map? Instead they were solid color. We were 8-1 or something, every day, including Saturdays, in a room with solid color walls, solid color desks, and a blackboard, and that’s it. Perhaps no wonder that I exercised my art and craft on what I had. I dismembered floppy disks, cassettes, speakers etc. and stuck them on the wall. I scribbled all over my desk.

At some point I got an Amiga 1000 (my trajectory was Spectrum 48K, Commodore 64, Amiga 1000). Naturally I wanted to program, but had zero leads. Unlike today, it was very hard to get started. Interestingly, people more experienced than me had the same complaint, like “when I was 13 myself good luck finding an assembler.” Actually, I think things will continue to move in this direction. Even today, learning something isn’t that easy, and one can imagine how in 20 years you’ll have tutorials precisely tailored to your background, instead of having to zap through youtube to find the small step you’re missing.

So for a while I was stuck fiddling with startup sequences and shell commands. I remember my parents puzzled at why I wasn’t doing anything fancy like on the C64.
“You’re still at popcli” (a type of shell, known back then as CLI, command line interface) they told me once — I am cursed with good memory.
My reply was “You need a program to write a program.” They looked puzzled. (And so was I, after all, I didn’t need one on the C64.)

My turning point occurred when I did one of my stupid things. I was balancing myself on the top beam of a swing. Naturally, I fell, didn’t land right, and injured my ankle. I was stuck in my room for a month, and one day Marco showed up and brought me the Amiga hardware reference manual, a book we had overheard was critical. I thanked him and I remember him saying: “I am doing it for me.” This book became my bible. I thrashed the stupid C compilers, got an assembler, and started “bashing metal” and having fun.

Then there was the store. I don’t remember how I ended up there. It sold games, so maybe I was just there to buy games. But I never bought a new game — only pirate — so the explanation doesn’t stand. Anyway, we were there and the person there was a techno-musician who knew people who wanted to make a game on Nathan Never, a pretty high-profile graphic novel series in Italy.

To this day I am shocked they didn’t find anyone else, since as I said it’s pretty high-profile. Maybe the programmer wanted too much money, or ditched them last moment and they needed the game fast. Who knows. I had just barely started programming on Amiga, but… I know blitter, I know copper; I am obviously ready for a major project.

So we signed the contract, and I insisted on some money upfront which I got. A few Ks. The development of the game was covered in games magazines, which other people in our high school were devouring. They were shocked to find out the team was us! Waking around, we would pass by a store and find the box of the game on display.

As part of my deal I managed to get an Amiga 3000 tower, a one-of-a-kind machine, which for a kid like me was a dream. Before that, I didn’t have enough memory to play the game from the assembler with the graphics loaded, so when I tested it I would see dots instead of sprites. Marco, who did the graphics, at the beginning didn’t have a color monitor, and would pick colors from the hex code, quite cool. I brought the 3000T to our vacation that summer, and instead of going to the sea (which I hated) I stayed indoor to program. Naturally, I spent 50% (easily) of that time programming a script that would compile an animation through a landscape of fractal mountains. The final animation was quite cool.

I wish the game was more fun to play. It isn’t really my fault: no experience, no time, and crucially the people who imposed the game design on us were not players but exclusively concerned with showing the main character, whose frames occupy most of the memory. More than the game they cared about the graphic novel that came with it in the box. Of all the people buzzing around the game, I was the only one who actually played computer games (I still do). Still, of course, I could have improved the gameplay. Instead, on an ultra-tight deadline, I decided to embark on a 3D “escape from the tunnel” last level, something they didn’t ask for (they were happy with an animation, which would have cost me zero effort) and that probably almost noone has seen, since to get there you need to beat two grueling platform levels a puzzle level, with one life and no save state. (The 3D level starts at 20:09 in this long play.) And this is what it means to be 14.

On the bright side, however, perhaps the game has its unique charm, and today it can be played on a hard disk through the emulator, even though the game was not designed to be installed on a hard disk. And this is great because playing the game from the disks is really painful, despite or in part because of a crazy color hack to make a 3D “change disk” message (another uncalled-for feature). And it’s a good feeling that after 30+ years some people are still watching and playing the game.

Mathematics of the impossible: Computational Complexity, Chapter 3: The grand challenge

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.

---

Contents

1 The grand challenge
1.1 Information bottleneck: Palindromes requires quadratic time on TMs
1.2 Counting: impossibility results for non-explicit functions
1.3 Diagonalization: Enumerating machines
1.3.1
1.4 Circuits
1.4.1 The circuit won’t fit in the universe: Non-asymptotic, cosmological results
1.5 Problems

As mentioned in Chapter ??, our ability to prove impossibility results related to efficient computation appears very limited. We can now express this situation more precisely with the models we’ve introduced since then.

It is consistent with our knowledge that any problem in a standard algorithm textbook can be solved

1. in Time on a TM, and
2. in Time on a 2-TM, and
3. by circuits of size .

Note that 2. implies 1. by Theorem ??.

In this chapter we begin to present several impossibility results, covering a variety of techniques which will be used later as well. As hinted above, they appear somewhat weak. However, jumping ahead, there is a flip side to all of this:

1. At times, contrary to our intuition, stronger impossibility results are actually false. One example appears in Chapter ??. A list will be given later.
2. Many times, the impossibility results that we can prove turn out to be, surprisingly, just “short” of proving major results. Here by “major result” I mean a result that would be phenomenal and that was in focus long before the connection was established. We will see several examples of this (section º??, section º??).
3. Yet other times, one can identify broad classes of proof techniques, and argue that impossibility results can’t be proved with them (section º??).

Given this situation, I don’t subscribe to the general belief that stronger impossibility results are true and we just can’t prove them.

1.1 Information bottleneck: Palindromes requires quadratic time on TMs

Intuitively, the weakness of TMs is the bottleneck of passing information from one end of the tape to the other. We now show how to formalize this and use it show that deciding if a string is a palindrome requires quadratic time on TMs, which is tight and likely matches the time in Exercise ??. The same bound can be shown for other functions; palindromes just happen to be convenient to obtain matching bounds.

Theorem 1.1. for any .

More precisely, for every and , an -state TM that decides if an -bit input is a palindrome requires time .

The main concept that allows us to formalize the information bottleneck mentioned above is the following.

Definition 1.1. A crossing sequence of a TM M on input and boundary , abbreviated -CS, is the sequence of states that is transitioning to when crossing cell boundary (i.e., going from Cell to or vice versa) during the computation on .

The idea in the proof is very interesting. If accepts inputs and and those two inputs have the same -CS for some , then we can “stitch together” the computation of on and at boundary to create a new input that is still accepted by . The input is formed by picking bits from to the left of cell boundary and bits from to the right of :

The proof that is still accepted is left as an exercise.

Now, for many problems, input should not be accepted by , and this gives a contradiction. In particular this will be be the case for palindromes. We are going to find two palindromes and that have the same -CS for some , but the corresponding is not a palindrome, yet it is still accepted by . We can find these two palindromes if takes too little time. The basic idea is that if runs in time , because -CSs for different correspond to different steps of the computation, for every input there is a value of such that the -CS is short, namely has length at most . If is much less than , the length of this CS is much less than , from which we can conclude that the number of CSs is much less than the number of inputs, and so we can find two inputs with the same CS.

Proof. Let be divisible by four, without loss of generality, and consider palindromes of the form

where and is the reverse of .

Assume there are in and in the middle part, i.e., , so that the -CS of on and is the same. Then we can define which is not a palindrome but is still accepted by , concluding the proof.

There remains to prove that the assumption of Theorem 1.1 implies the assumption in the previous paragraph. Suppose runs in time . Since crossing sequences at different boundaries correspond to different steps of the computation, for every there is a value of in the middle part such that the -CS of on has length . This implies that there is an in the middle s.t. there are inputs for which the -CS of on has length .

For fixed , the number of -CS of length is .

Hence there are for which and have the same -CS whenever . Taking logs one gets . QED

Exercise 1.1. For every and describe an -state TM deciding palindromes in time (matching Theorem 1.1).

Exercise 1.2. Let . Show , and prove this is tight up to constants.

One may be tempted to think that it is not hard to prove stronger bounds for similar functions. In fact as mentioned above this has resisted all attempts!

1.2 Counting: impossibility results for non-explicit functions

Proving the existence of hard functions is simple: Just count. If there are more functions than efficient machines, some function is not efficiently computable. This is applicable to any model; next we state it for TMs for concreteness. Later we will state it for circuits.

Theorem 1.2. There exists a function that cannot be computed by a TM with states unless , regardless of time.

Proof. The number of TMs with states is and each TM computes at most one function (it may compute none, if it does not stop). The number of functions on bits is . Hence if some function cannot be computed. QED

Note this bound is not far from that in Exercise ??.

It is instructive to present this basic result as an application of the probabilistic method:

Proof. Let us pick uniformly at random. We want to show that

Indeed, if the probability is less than than some function exists that cannot be computed. By a union bound we can say that this probability is

where the sum is over all -state machines. Each probability in the sum is , since is fixed. The number of -state machines is . So the sum is , and we can conclude as before taking logs. QED

1.3 Diagonalization: Enumerating machines

Can you compute more if you have more time? For example, can you write a program that runs in time and computes something that cannot be computed in time ? The answer is yes for trivial reasons if we allow for non-boolean functions.

Exercise 1.3. Give a function in .

The answer is more interesting if the functions are boolean. Such results are known as time hierarchies, and a generic technique for proving them is diagonalization, applicable to any model.

We first illustrate the result in the simpler case of partial functions, which contains the main ideas. Later we discuss total functions.

Theorem 1.3. There is a partial function in such that any TM computing it runs in time , for any .

In other words, .

Proof. Consider the TM that on input of length runs on until it stops and then complements the answer. (We can use a simple encoding of these pairs, for example every even-position bit of the description of is a .)

Now define to be the subset of pairs s.t.  runs in time on inputs of length , and .

On these inputs, runs in time , as desired. To accomplish this, can begin by making a copy of in time . Then every step of the computation of can be simulated by with steps, always keeping the description of to the left of the head.

Now suppose computes the same function as in time . Note that falls in the domain of the function, for sufficiently large, using that . Now consider running on . We have by supposition, but is the complement of , contradiction. QED

This proof is somewhat unsatisfactory; in particular we have no control on the running time of on inputs not in . It is desirable to have a version of this fundamental result for total functions. Such a version is stated next. It requires additional assumptions on and a larger gap between the running times. Perhaps surprisingly, as we shall discuss, both requirements are essential.

Theorem 1.4. Let be a function. Suppose that is in .

There is a total function in that cannot be computed by any TM in time .

The assumption about is satisfied by all standard functions, including all those in this book. (For example, take . The corresponding is then . To compute on input of bits we can first compute in time (Exercise ??). This is a number of bits. We can then square this number in time . Note that the time to compute is dominated by the term coming from computing , which does not depend on and is much less than the in the assumption.) The assumption cannot be removed altogether because there exist pathological functions for which the result is false.

The proof is similar to that of Theorem 1.3. However, to make the function total we need to deal with arbitrary machines, which may not run in the desired time or even stop at all. The solution is to clock in a manner similar to the proof of the universal machine, Lemma ??.

Also, we define a slightly different language to give a stronger result – a unary language – and to avoid some minor technical details (the possibility that the computation of erases the input).

We define a TM that on input obtains a description of a TM , computes , and then simulates on input for steps in a way similar to Lemma ??, and if stops then outputs the complement of the output of ; and if does not stop then stops and outputs anything. Now computes a function in time about . We argue that this function cannot be computed in much less time as follows. Suppose some TM computes the function in time somewhat less than . Then we can pick an for which obtains the description of this , and the simulation always stops. Hence, for that we would obtain , which is a contradiction.

However, there are interesting differences with the simulation in Lemma ??. In that lemma the universal machine was clocking the steps of the machine being simulated. Now instead we need to clock the steps of itself, even while is parsing the description of to compute its transition function. This is necessary to guarantee that does not waste time on big TM descriptions.

Whereas in Lemma ?? the tape was arranged as

it will now be arranged as

which is parsed as follows. The description of is , is in state , the tape of contains and the head is on the left-most symbol of . The integer is the counter decreased at every step

Proof. Define TM that on input :

1. Compute .
2. Compute . Here is obtained from by removing all left-most zeroes until the first . I.e., if then . This is similar to the fact that a program does not change if you add, say, empty lines at the bottom.
3. Simulate on , reducing the counter at every step, including those parsing , as explained before.
4. If stops before the counter reaches , output the complement of its output. If the counter reaches stop and output anything.

Running time of .

1. Computing is similar to Exercise ??. By assumption is computable in time . Our definition of computation allows for erasing the input, but we can keep around spending at most another factor. Thus we can compute in time . Finally, in case it was erased, we can re-compute in time by keeping a counter (initialized to a copy of ).
2. This takes time : simply scan the input and remove zeroes.
3. Decreasing the counter takes steps. Hence this simulation will take time.

Overall the running time is .

Proof that the function computed by requires much time. Suppose some TM computes the same function as . Consider inputs where . Parsing the description of to compute its transition function takes time , a value that depends on only and not on . Hence will simulate steps of . If stops within that time (which requires to be larger than , and so and sufficiently large compared to ) then the simulation terminates and we reach a contradiction as explained before. QED

The extra factor cannot be reduced because of the surprising result presented in Theorem 1.5 showing that, on TMs, time equals time for computing total functions.

However, tighter time hierarchies hold for more powerful models, like RAMs. Also, a time hierarchy for total functions for is… an open problem! But a hierarchy is known for partial functions.

Exercise 1.4. (1) State and prove a tighter time hierarchy for Time (which recall corresponds to RAMs) for total functions. You don’t need to address simulation details, but you need to explain why a sharper separation is possible.

(2) Explain the difficulty in extending (1) to .

(3) State and prove a time hierarchy for for partial functions.

1.3.1

In this subsection we prove the result in the title, which we also mentioned earlier. First let us state the result formally.

Theorem 1.5. [1, 2] Let be in for a . Then .

Note that time is barely enough to scan the input. Indeed, the corresponding machines in Theorem 1.5 will only move the head in one direction.

The rest of this section is devoted to proving the above theorem. Let be a machine for witnessing the assumption of the theorem. We can assume that stops on every input (even though our definition of time only applies to large enough inputs), possibly by adding to the time, which does not change the assumption on . The theorem now follows from the combination of the next two lemmas.

Lemma 1.1. Let be a TM running in time . Then on every input every -CS with has length .

Proof. For an integer let be a shortest input such that there exists for which the -CS in the computation of on has length . Let .

Exercise 1.5. Prove for .

There are tape boundaries within or bordering . If we pick a boundary uniformly at random, the average length of a CS on is . Hence there are choices for s.t. the -CS on has length .

The number of such crossing sequences is

Hence, the same crossing sequence occurs at positions , using that is large enough.

Of these four, one could be the CS of length from the definition of . Of the other three, two are on the same side of . We can remove the corresponding interval of the input without removing the CS of length . Hence we obtained a shorter input with a CS of length . Contradiction. QED

Lemma 1.2. Suppose is computable by a TM such that on every input , every -CS with has length . Then is computable in time by a TM with states that only moves the head in one direction.

Exercise 1.6. Prove this.

1.4 Circuits

The situation for circuits is similar to that of 2-TMs, and by Theorem ?? we know that proving bounds on circuits is harder than for 2-TMs. Even a bound of is unknown. The following is a circuit version of Theorem 1.2. Again, the bound is close to what we saw in Theorem ??.

Theorem 1.6. [3] There are functions that require circuits of size , for every .

One can prove a hierarchy for circuit size, by combining Theorem 1.6 and Theorem ??. As stated, the results give that circuits of size compute more functions than those of size . In fact, the “” in the theorems is small, so one can prove a sharper result. But a stronger and more enjoyable argument exists.

Theorem 1.7. [Hierarchy for circuit size] For every and there is a function that can be computed by circuits of size but not by circuits of size .

Proof. Consider a path from the all-zero function to a function which requires circuits of size , guaranteed to exist by Theorem 1.6, changing the output of the function on one input at each step of the path. Let be the first function that requires size , and let be the function right before that in the path. Note that has circuits of size , and can be computed from by changing the value on a single input. The latter can be implemented by circuits of size . QED

Exercise 1.7. Prove a stronger hierarchy result for alternating circuits, where the “” in Theorem 1.7 is replaced with “.”

In fact, this improvement is possible even for (non aternating) circuits, see Problem 1.2.

1.4.1 The circuit won’t fit in the universe: Non-asymptotic, cosmological results

Most of the results in this book are asymptotic, i.e., we do not explicitly work out the constants because they become irrelevant for larger and larger input lengths. As stated, these results don’t say anything for inputs of a fixed length. For example, any function on bits is in Time.

However, it is important to note that all the proofs are constructive and one can work out the constants, and produce non-asymptotic results. We state next one representative example when this was done. It is about a problem in logic, an area which often produces very hard problems.

On an alphabet of size , the language used to write formulas includes first-order variables that range over , second-order variables that range over finite subsets of , the predicates “” and “” where and denote first-order variables and denotes a set variable, and standard quantifiers, connectives, constants, binary relation symbols on integers, and set equality. For example one can write things like “every finite set has a maximum:”

Theorem 1.8. [4] To decide the truth of logical formulas of length at most in this language requires a circuit containing at least gates. So even if each gate were the size of a proton, the circuit would not fit in the known universe.

Their result applies even to randomized circuits with error , if is replaced with . (We can define randomized circuits analogously to BPTime.)

1.5 Problems

Problem 1.1. Hierarchy Theorem 1.4 only gives a function that cannot be computed fast on all large enough input lengths: it is consistent with the theorem that can be computed fast on infinitely many input lengths.

Give a function mapping to that is computable in time but such that for any TM running in time the following holds. For every and every such that .

Hint: Note the range of . Can this result hold as stated with range ?

Problem 1.2. Replace “” in Theorem 1.7 with “.”

Problem 1.3. Prove that

This shows Theorem 1.5 is tight, and gives an explicit problem witnessing the time-hierarchy separation in Theorem 1.4, for a specific time bound. For the negative result, don’t use pumping lemmas or other characterization results not covered in this book.

Problem 1.4. The following argument contradicts Theorem 1.4; what is wrong with it?

“By Theorem 1.5, . By padding (Theorem 1.5), . Hence ”

References

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

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

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

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