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.

Mathematics of the impossible: Computational Complexity, Chapter 2

Click here for PDF version (which has better rendering of pictures, tables, etc.)
Click here for all blog posts on this.

 

Contents

2 The alphabet of Time
 2.1 Tape machines (TMs)
  2.1.1 You don’t need much to have it all
  2.1.2 Time complexity, P, and EXP
  2.1.3 The universal TM
 2.2 Multi-tape machines (MTMs)
 2.3 Circuits
 2.4 Rapid-access machines (RAMs)
 2.5 A challenge to the computability thesis
  2.5.1 Robustness of BPP: Error reduction and tail bounds for the sum of random variables
  2.5.2 Does randomness buy time?
  2.5.3 Polynomial identity testing
  2.5.4 Simulating BPP by circuits
  2.5.5 Questions raised by randomness
 2.6 Inclusion extend “upwards,” separations downwards
 2.7 Problems

 

 

 

Chapter 2
The alphabet of Time

 

https://xkcd.com/163/

 

The details of the model of computation are not too important if you don’t care about power differences in running times, such as the difference between solving a problem on an input of length in time vs. time . But they matter if you do.

The fundamentals features of computation are two:

• Locality. Computation proceeds in small, local steps. Each step only depends on and affects a small amount of “data.” For example, in the grade-school algorithm for addition, each step only involves a constant number of digits.
• Generality. The computational process is general in that it applies to many different problems. At one extreme, we can think of a single algorithm which applies to an infinite number of inputs. This is called uniform computation. Or we can design algorithms that work on a finite set of inputs. This makes sense if the description of the algorithm is much smaller than the description of the inputs that can be processed by it. This setting is usually referred to as non-uniform computation.

Keep in mind these two principles when reading the next models.

---

 

 

Figure 2.1: Computational models for Time. An arrow from to means that can simulate efficiently (from time to ).

---

2.1 Tape machines (TMs)

Tape machines are equipped with an infinite tape of cells with symbols from the tape alphabet , and a tape head lying on exactly one cell. The machine is in one of several states, which you can think of as lines in a programming language. In one step the machine writes a symbol where the head points, changes state, and moves the head one cell to the right or left. Alternatively, it can stop. Such action depends only on the state of the machine and the tape symbol under the head.

We are interested in studying the resources required for computing. Several resources are of interest, like time and space. In this chapter we begin with time.

Definition 2.1. [8]A tape machine (TM) with states is a map (known as transition or step)

where is the tape alphabet. The alphabet symbol _ is known as blank.

A configuration of a TM encodes its tape content, the position of the head on the tape, and the current state. It can be written as a triple ) where maps the integers to and specifies the tape contents, is an integer indicating the position of the head on the tape, and is the state of the machine.

A configuration ) yields ) if and and elsewhere, and similarly it yields ) if and and elsewhere, and finally it yields itself if .

We say that a TM computes on input in time (or in steps) if, starting in configuration where and is blank elsewhere, it yields a sequence of configurations where the last one is where has a Stop instruction, and and is blank elsewhere.

 

Describing TMs by giving the transition function quickly becomes complicated and uninformative. Instead, we give a high-level description of how the TM works. The important points to address are how the head moves, and how information is moved across the tape.

Example 2.1. On input we wish to compute (i.e., we think of as an integer in binary, and increment by one). This can be accomplished by a TM with states as follows. Move the head to the least significant bit of . If you read a , write a , move the head to the beginning, and stop. If instead you read a , write a , move the head by one symbol, and repeat. If you reach the beginning of the input, shift the input by one symbol, append a , move the head to the beginning and stop.

The TM only does a constant number of passes over the input, so the running time is .

 

Example 2.2. On an input we wish to decide if it has the the same number of zeros and ones. This can be done as follows. Do a pass on the input, and cross off one 0 and one 1 (by replacing them with tape symbol #). If you didn’t find any 0 or or , accept (that is, write on the tape and stop). If only find a but not a , or vice versa, reject.

Since every time we do a pass we cross at least two symbols, the running time is .

 

Exercise 2.1. Describe a TM that decides if a string is palindrome, and bound its running time.

 

Exercise 2.2. Describe a TM that on input computes in binary in time .

 

TMs can compute any function if they have sufficiently many states:

Exercise 2.3. Prove that every function can be computed by a TM in time using states.

 

 

2.1.1 You don’t need much to have it all

How powerful are tape machines? Perhaps surprisingly, they are all-powerful.

 

 

Power-time computability thesis.

For any “realistic” computational model there is such that: Anything that can be computed on in time can also be computed on a TM in time .

 

This is a thesis, not a theorem. The meaning of “realistic” is a matter of debate, and one challenge to the thesis is discussed in section º2.5.

However, the thesis can be proved for many standard computational models, which include all modern programming languages. The proofs aren’t hard. One just tediously goes through each instruction in the target model and gives a TM implementation. We prove a representative case below (Theorem 2.6) for rapid-access machines (RAMs), which are close to how computers operate, and from which the jump to a programming language is short.

Given the thesis, why bother with TMs? Why not just use RAMs or a programming language as our model? In fact, we will basically do that. Our default for complexity will be RAMs. However, some of the benefits of TMs remain

• TMs are easier to define – just imagine how more complicated Definition 2.1 would be were we to use a different model. Whereas for TMs we can give a short self-contained definition, for other models we have to resort to skipping details. There is also some arbitrariness in the definition of other models. What operations exactly are allowed?
• TMs allow us to pinpoint more precisely the limits of computation. Results such as Theorem ?? are easier to prove for TMs. A proof for RAM would first go by simulating RAM by a TM.
• Finally, TMs allow us to better pinpoint the limits of our knowledge about computation; we will see several examples of this.

In short, RAMs and programming languages are useful to carry computation, TMs to analyze it.

 

2.1.2 Time complexity, P, and EXP

We now define our first complexity classes. We are interested in solving a variety of computational tasks on TMs. So we make some remarks before the definition.

• We often need to compute structured objects, like tuples, graphs, matrices, etc. One can encode such objects in binary by using multiple bits. We will assume that such encodings are fixed and allow ourselves to speak of such structures objects. For example, we can encode a tuple where by repeating each bit in each twice, and separate elements with .
• We can view machines as computing functions, or solving problems, or deciding sets, or deciding languages. These are all equivalent notions. For example, for a set , the problem of deciding if an input belongs to , written , is equivalent to computing the boolean characteristic function which outputs if the input belongs to , and otherwise. We will use this terminology interchangeably. In general, “computing a function” is more appropriate terminology when the function is not boolean.
• We allow partial functions, i.e., functions with a domain that is a strict subset of . This is a natural choice for many problems, cf. discussion in section º??.
• We measure the running time of the machine in terms of the input length, usually denoted . Input length can be a coarse measure: it is often natural to express the running time in terms of other parameters (for example, the time to factor a number could be better expressed in terms of the number of factors of the input, rather than its bit length). However for most of the discussion this coarse measure suffices, and we will discuss explicitly when it does not.
• We allow non-boolean outputs. However the running time is still only measured in terms of the input. (Another option which sometimes makes sense, it to bound the time in terms of the output length as well, which allows us to speak meaningfully of computing functions with very large outputs, such as exponentiation.)
• More generally, we are interested in computing not just functions but relations. That is, given an input we wish to compute some that belongs to a set . For example, the problem at hand might have more than one solution, and we just want to compute any of them.
• We are only interested in sufficiently large , because one can always hard-wire solutions for inputs of fixed size, see Exercise 2.3. This allows us to speak of running times like without worrying that it is not suitable when is small (for example, , so the TM could not even get started). This is reflected in the in the definition.

With this in mind, we now give the definition.

Definition 2.2. [Time complexity classes – boolean] Let be a function. ( denotes the natural numbers .) TM-Time denotes the functions that map bit strings from a subset to a set for which there exists a TM such that, on any input of length , computes within steps and .

 

 

We will not need to deal with relations and partial functions until later in this text.

Also, working with boolean functions, i.e., functions with range slightly simplifies the exposition of a number of results we will see later. To avoid an explosion of complexity classes, we adopt the following convention.

 

Convention about complexity classes:

  Unless specified otherwise, inclusions and separations among complexity classes refer to boolean functions. For example, an expression like means that every boolean function in is in .

 

As hinted before, the definition of is robust. In the next few sections we discuss this robustness in more detail, and also introduce a number of other central computational models.

 

2.1.3 The universal TM

Universal machines can simulate any other machine on any input. These machines play a critical role in some results we will see later. They also have historical significance: before them machines were tailored to specific tasks. One can think of such machines as epitomizing the victory of software over hardware: A single machine (hardware) can be programmed (software) to simulate any other machine.

Lemma 2.1. There is a TM that on input where is a TM, is an integer, and is a string:

-Stops in time ,

-Outputs if the latter stops within steps on input .

 

 

Proof. To achieve the desired speed, the idea is to maintain the invariant that and are always next to the tape head. After the simulation of each step of the tape of will contain

where 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. Computing the transition of takes time . Decreasing the counter takes time . To move and next to the tape head takes time. QED

 

 

2.2 Multi-tape machines (MTMs)

Definition 2.3. A -TM is like a TM but with tapes, where the heads on the tapes move independently. The input is placed on the first tape, and all other tapes are initialized to _. The output is on the first tape. is defined analogously to

 

Exercise 2.4. Prove that Palindromes is in . Compare this to the run-time from the the TM in Exercise 2.1.

 

The following result implies in particular that is unchanged if we define it in terms of TMs or .

Theorem 2.1. for any and .

 

Exercise 2.5. Prove this. Note: Use TMs as we defined them, this may make a step of the proof less obvious than it may seem.

 

A much less obvious simulation is given by the following fundamental result about MTMs. It shows how to reduce the number of tapes two two, at very little cost in time. Moreover, the head movements of the simulator are restricted in a sense that at first sight appears too strong.

Theorem 2.2. [3, 6], for every function . Moreover, the 2-TM is oblivious: the movement of each tape head depends only on the length of the input.

 

Using this results one can prove the existence of universal MTMs similar to the universal TMs in Lemma 2.1.

---

 

 

Figure 2.2: A circuit computing the Xor of two bits.

---

 

---

 

 

Figure 2.3: An alternating circuit.

---

 

2.3 Circuits

We now define circuits. It may be helpful to refer to figure 2.2 and figure 2.3.

Definition 2.4. A circuit, abbreviated Ckt, is a directed acyclic graph where each node is one of the following types: an input variable (fan-in ), an output variable (fan-in ), a negation gate (fan-in ), an And gate (fan-in ), or an Or gate (fan-in ). The fan-in of a gate is the number of edges pointing to the gate, the fan-out is the number of edges pointing away from the gate.

An alternating circuit, abbreviated AltCkt, is a circuit with unbounded fan-in Or and And gates arranged in alternating layers (that is, the gates at a fixed distance from the input all have the same type). For each input variable the circuit has both and as input.

A DNF (resp. CNF) is an AltCkt whose output is Or (resp. And). The non-ouput gates are called terms (resp. clauses).

denotes the set of function that, for all sufficiently large , on inputs of length have circuits with gates; input and output gates are not counted.

The size of a circuit is the number of gates.

 

Exercise 2.6. [Pushing negation gates at the input] Show that for any circuit with gates and depth there is a monotone circuit (that is, a circuit without Not gates) with gates and depth such that for any : .

 

Often we will consider computing functions on small inputs. In such cases, we can often forget about details and simply appeal to the following result, which gives exponential-size circuits which are however good enough if the input is really small. In a way, the usefulness of the result goes back to the locality of computation. The result, which is a circuit analogue of Exercise 2.3, will be extensively used in this book.

Theorem 2.3. Every function can be computed by

(1) [5] circuits of size , and

(2) A DNF or CNF with gates (in particular, circuits of size ).

 

Exercise 2.7. Prove that the Or function on bits has circuits of size . Prove Item (2) in Theorem 2.3. Prove a weaker version of Item (1) in Theorem 2.3 with bound .

 

Exercise 2.8. Prove that the sum of two -bit integers can be computed by circuits with gates, and by alternating circuits of depth and size .

 

We now show that circuits can simulates TMs. We begin with a simple but instructive simulation which incurs a quadratic loss, then discuss a more complicated and sharper one.

Theorem 2.4. Suppose an -state TM computes in time . Then .

 

For this proof it is convenient to represent a configuration of a TM in a slightly different way, as a string over the alphabet . String

with indicates that (1) the tape content is with blanks on either side, (2) the machine is in state , and (3) the head of the machine is on the tape symbol in the string.

Locality of computation here means that one symbol in a string only depends on the symbols corresponding to the same tape cell in the previous step and its two neighbors – three symbols total – because the head only moves in one step.

 

Proof of Theorem 2.4.  Given a TM with states consider a matrix , a.k.a. the computation table, where row is the configuration at time . The starting configuration in Row 1 has the head in the middle cell. Note we don’t need more than cells to the right or left because the head moves only by one cell in one step. Next we claim that Row can be computed from Row by a Ckt with gates. This follows by locality of computation, where note each entry in Row can be computed by a Ckt of size , by Theorem 2.3.

Stacking such circuits we obtain a circuit of size which computes the end configuration of them TM.

There remains to output the value of the function. Had we assumed that the TM writes the output in a specific cell, we could just read it off by a circuit of size . Without the assumption, we can have a circuit which outputs 1 on iff and (i.e., if is a that is under the TM’s head). Taking an Or such circuits applied to every entry in the last row of concludes the proof. QED

 

The simulation in Theorem 2.4. incurs a quadratic loss. However, a better simulation exists. In fact, this applies even to -TMs.

Theorem 2.5. [6] Suppose an -state -TM computes in time . Then .

 

Exercise 2.9. Prove Theorem 2.5 assuming Theorem 2.2.

 

However, we won’t need it, as we will work with another model which is closer to how computers operate. And for this model we shall give a different and simpler “simulation” by circuits in Chapter ??.

In the other direction, TMs can simulate circuits if they have enough states. In general, allowing for the number of states to grow with the input length gives models with “hybrid uniformity.”

Exercise 2.10. Suppose that has circuits with gates. Show that can be computed by a TM with states in time .

 

 

2.4 Rapid-access machines (RAMs)

 

 

 

“In some sense we are therefore merely making concrete intuitions that already pervade the literature. A related model has, indeed, been treated explicitly” […] [2]

 

 

The main feature that’s missing in all models considered so far is the ability to access a memory location in one time step. One can augment TMs with this capability by equipping them with an extra addressing tape and a special “jump” state which causes the head on a tape to move in one step to the address on the address tape. This model is simple enough to define, and could in a philosophical sense be the right model for how hardware can scale, since we charge for the time to write the address.

 

However, other models are closer to how computers seem to operate, at least over small inputs. We want to think of manipulating small integers and addresses as constant-time operations, as one typically has in mind when programming. There is a variety of such models, and some arbitrariness in their definition. Basically, we want to think of the memory as an array of cells of bits and allow for typical operations of them, including addressing arithmetic and indirect addressing: reading and writing the cell indexed by another cell.

One issue that arises is how much memory the machine should have and consequently how big should be. There are two main options here. For “typical programming,” we have a fixed memory size and time bound in mind, for example and . A good choice then is to set bits.

This however makes it harder to compare machines with different memory bounds. Also in some scenarios the memory size and the time bound are not fixed. This occurs for example when simulating another machine. To handle such scenarios we can start with a memory of cells,and a cell size of bits, enough to access the input. We then equip machines with the operation MAlloc which increases the memory (i.e., ) by one, and always sets . Note the latter operation may increase by . The MAlloc operation is akin to the TM’s tape head wandering into unknown cells.

There are also two options for how the input is given to the machine. The difference doesn’t matter if you don’t care about factors in time, but it matters if you do. For many problems, like sorting, etc. we think of the input and the output as coming in cells of bits. (Typically, , and one can simulate such cells with cells with bits.) In this case, the RAM is computing a function and the input to the RAM is given accordingly. This is what one often has in mind when writing programs that involve numbers. For other problems, it is natural to just give one bit of the input in each cell. That is, the RAM is computing and bit of the input is placed in the input cells. We will not be concerned too much with small factors and so we pick the second choice for simplicity.

Definition 2.5. A -bit -line rapid-access machine (RAM) with cells consists of a memory array of cells of bits, registers of bits, and a program of lines.

Each line of the program contains an instruction among the following:

• Standard arithmetical and logical operations, such as etc.
• , called a Read operation, which reads the memory cell and copies its content into ,
• , called a Write operation, which writes into memory cells , memory cell and copies its content into ,
• MAlloc which increases by and, if also increases by ,
• Stop.

Read and write operations out of boundary indices have no effect.

On an input , the RAM starts the computation with cells of memory. The input is written in cells , while contains the length of the input.

The output is written starting in cell .

 

We use RAMs as our main model for time inside .

Definition 2.6. is defined as but for RAMs instead of TMs.

 

Theorem 2.6. , for any .

 

Exercise 2.11. Prove it.

 

What is the relationship between circuits and RAMs? If a “description” of the circuit is given, then a RAM can simulate the circuit efficiently. The other way around is not clear. It appears that circuits need a quadratic blow-up to simulate RAMs.

Exercise 2.12. Give a function in but which requires circuits of size .

 

There are universal RAMs that can simulate any other RAM with only a constant-factor overhead, unlike the logarithmic-factor overhead for tape machines.

Lemma 2.2. There is a RAM that on input where is a RAM, is an integer, and is an input

-Stops in time ,

-Outputs if the latter stops within steps on input .

 

 

Proof. Throughout the computation, will keep track of the memory size and cell-size of . These are initialized as in the initial configuration of on input , whereas starts with bigger values, since its input also contains and . Let be the first cell where the input starts. Memory location of is mapped to during the simulation. When performs an operations among registers, simulates that with its own registers, but discards the data that does not fit into bits.

After each step, decreases the counter. The counter can be stored in cells, one bit per cell. The total number of operations to decrease such a counter from to is . Alternatively, we can think of the counter as being stored in a single register at the beginning of the simulation. Then decreasing the counter is a single operation. QED

 

 

2.5 A challenge to the computability thesis

Today, there’s a significant challenge to the computability thesis. This challenge comes from… I know what you are thinking: Quantum computing, superposition, factoring. Nope. Randomness.

The last century or so has seen an explosion of randomness affecting much of science, and computing has been a leader in the revolution. Today, randomness permeates computation. Except for basic “core” tasks, using randomness in algorithms is standard. So let us augment our model with randomness.

Definition 2.7. A randomized (or probabilistic) RAM, written RRAM, is a RAM equipped with the extra instruction

• , which sets to a uniform value, independent of all previous random choices.

For a RRAM and a sequence we write for the execution of on input where the -th instruction is replaced with .

We refer to BPTime with error as the set of functions that map bit strings from a subset to a set for which there exists a RRAM such that, on any input of length , stops within steps and .

If the error is not specified then it is assumed to be . Finally, we define

 

 

Exercise 2.13. Does the following algorithm show that deciding if a given integer is prime is in ? “Pick a uniform integer . Check if divides .”

 

Today, one usually takes , not , for “feasible computation.” Thus it is natural to investigate how robust is.

 

2.5.1 Robustness of BPP: Error reduction and tail bounds for the sum of random variables

The error in the definition of BPTime is somewhat arbitrary because it can be reduced. The way you do this is natural. For boolean functions, you repeat the algorithm many times, and take a majority vote. To analyze this you need probability bounds for the sum of random variables (corresponding to the outcomes of the algorithm).

Theorem 2.7. Let be i.i.d. boolean random variables with . Then for we have , where

is the divergence.

 

Now one can get a variety of bounds by bounding divergence for different settings of parameter. We state one such bound which we use shortly.

Fact 2.1. .

 

Exercise 2.14. Plot both sides of Fact 2.1 as a function of . (Hint: I used https://www.desmos.com/calculator)

 

Using this bound we can prove the error reduction stated earlier.

Theorem 2.8. [Error reduction for BPP] For boolean functions, the definition of BPP (Definition 2.7) remains the same if is replaced with or , for any constant .

 

 

Proof. Suppose that is in with error and let be the corresponding RRAM. On an input , let us run times , each time with fresh randomness, and take a majority vote. The new algorithm is thus

This new algorithm makes a mistake iff at least runs of make a mistake. To analyze this error probability we invoke Theorem 2.7 where iff run of the algorithm makes a mistake, i.e., , and . By Fact 2.1 we obtain an error bound of

as desired. The new algorithm still runs in power time, for fixed and . QED

 

Exercise 2.15. Consider an alternative definition of , denoted , which is analogous to except that the requirement that the machine always stops within steps is relaxed to “the expected running time of the machine is ”

Show that defining with respect to or is equivalent.

 

Exercise 2.16. Consider biased RRAMs which are like RRAMs except that the operation Rand returns one bit which, independently from all previous calls to Rand, is with probability and with probability . Show that BPP does not change if we use biased RRAMs.

 

 

2.5.2 Does randomness buy time?

We can always brute-force the random choices in exponential time. If a randomized machine uses random bits then we simulate it deterministically by running it on each of the choices for the bits. A RRAM machine running in time has registers of bits. Each Rand operation gives a uniform register, so the machine uses bits. This gives the following inclusions.

Theorem 2.9. Time BPTime Time, for any function . In particular, .

 

 

Proof. The first inclusion is by definition. The idea for the second was discussed before, but we need to address the detail that we don’t know what is. One way to carry through the simulation is as follows. The deterministic machine initializes a counter to . For each value of it enumerates over the choices for the random bits, and runs the RRAM on each choice of , keeping track of its output on each choice, and outputting the majority vote. If it ever runs out of random bits, it increases by and restarts the process.

To analyze the running time, recall we only need . So the simulation runs the RRAM at most times, and each run takes time , where this last bound takes into account the overhead for incrementing the choice of , and redirecting the calls to to . QED

 

Now, two surprises. First, is the fastest deterministic simulation we can prove for RAMs, or even 2-TMs. On the other hand, and that is perhaps the bigger surprise, it appears commonly believed that in fact ! Moreover, it appears commonly believed that the overhead to simulate randomized computation deterministically is very small. Here the mismatch between our ability and common belief is abysmal.

However, we can do better for TMs. A randomized TMs has two transition functions and , where each is as in Definition 2.1. At each step, the TM uses or with probability each, corresponding to tossing a coin. We can define as but with randomized TMs instead of RRAMS.

Theorem 2.10. [9] , for any .

 

 

2.5.3 Polynomial identity testing

We now discuss an important problem which is in BPP but not known to be in P. In fact, in a sense to be made precise later, this is the problem in BPP which is not known to be in P. To present this problem we introduce two key concepts which will be used many times: finite fields, and arithmetic circuits.

Finite fields

A finite field is a finite set with elements and that is equipped with operations and that behave “in the same way” as the corresponding operations over the reals or the rationals. One example are the integers modulo a prime . For this gives the field with two elements where is Xor and is And. For larger you add and multiply as over the integers but then you take the result modulo .

The following summarizes key facts about finite fields. The case of prime fields suffices for the main points of this section, but stating things for general finite fields actually simplifies the exposition overall (since otherwise we need to add qualifiers to the size of the field).

Fact 2.2. [Finite fields] A unique finite field of size exists iff where is a prime and . This field is denoted .

Elements in the field can be identified with .

[7] Given , one can compute a representation of a finite field of size in time . This representation can be identified with plus an element of .

Given a representation and field elements computing and is in .

 

Fields of size are of natural interest in computer science. It is often desirable to have very explicit representations for such and other fields. Such representations are known and are given by simple formulas, and are in particular computable in linear time.

Arithmetic circuits

We now move to defining arithmetic circuits, which are a natural generalization of the circuits we encountered in section º2.3.

Definition 2.8. An arithmetic circuit over a field is a circuit where the gates compute the operations and over , or are constants, or are input variables. Such a circuit computes a polynomial mapping .

The PIT (polynomial identity testing) problem over : Given an arithmetic circuit over with input variables, does for every ?

 

The PIT problem over large fields is in but it is not known to be in . The requirement that the field be large is critical, see Problem ??.

Theorem 2.11. [PIT over large fields in ] Given an arithmetic circuit and a field of size we can solve PIT in

 

To prove this theorem we need the following fundamental fact.

Lemma 2.3. Let be a polynomial over a finite field with variables and degree . Let be a subset of , and suppose . The following are equivalent:

 

 

1. is the zero polynomial.
2. for every .
3. .

 

Proof and discussion of Lemma 2.3.  The implications are trivial, but note that for the latter we need . The implication requires more work. It is a multi-variate generalization of the fundamental fact that a non-zero univariate polynomial of degree has at most roots. The fundamental fact can be recovered setting and .

To prove the multi-variate generalization we proceed by induction on . The base case is the fundamental fact (which we will not prove). For larger write

 

If is not the zero polynomial then there is at least one such that is not the zero polynomial. Let be the largest such . Note that has degree at most . By induction hypothesis

For every choice of s.t. , the polynomial is a non-zero polynomial only in the variable . Moreover, its degree is at most by our choice of . Hence by the case the probability that is over the choice of is .

Overall,

QED

 

 

Proof of Theorem 2.11.  A circuit contains at most multiplication gates. Each multiplication gate at most squares the degree of its inputs. Hence computes a polynomial of degree . Let be a subset of size of . Assign uniform values from independently to each variables, and evaluate the circuit. If evaluates to everywhere then obviously the output will be . Otherwise, by Lemma 2.3, the probability we get a is . QED

 

Exercise 2.17. Show that the PIT problem over the integers is in BPP. (Hint: Use that the number of primes in is , for every , and that checking if a number is prime is in .)

 

The bound is a weak form of the prime number theorem. The weak form typically suffices in computer science, and has a simple and cute encoding proof.

 

2.5.4 Simulating BPP by circuits

While we don’t know if , we can prove that, like , BPP has power-size circuits.

Theorem 2.12. [1]

 

 

Proof. Let be in . By Theorem 2.8 we can assume that the error is , and let be the corresponding RRAM. Note

where the first inequality is a union bound.

Therefore, there is a fixed choice for that gives the correct answer for every input . This choice can be hardwired in the circuit, and the rest of the computation can be written as a circuit by Theorem 2.4. QED

 

Exercise 2.18. In this exercise you will practice the powerful technique of combining tail bounds with union bounds, which was used in the proof of Theorem 2.12.

An error-correcting code is a subset s.t. for any distinct , and differ in at least coordinates. Prove the existence of codes of size for a constant .

 

 

2.5.5 Questions raised by randomness

The introduction of randomness in our model raises several fascinating questions. First, does “perfect” randomness exists “in nature?” Second, do we need “perfect” randomness for computation? A large body of research has been devoted to greatly generalize Problem 2.16 to show that, in fact, even imperfect sources of randomness suffices for computation. Third, do we need randomness at all? Is ?

One of the exciting developments of complexity theory has been the connection between the latter question and the “grand challenge” from the next chapter. At a high level, it has been shown that explicit functions that are hard for circuits can be used to de-randomize computation. In a nutshell, the idea is that if a function is hard to compute then its output is “random,” so can be used instead of true randomness. The harder the function the less randomness we need. At one extreme, we have the following striking connection:

Theorem 2.13. [4] Suppose for some there is a function in which on inputs of length cannot be computed by circuits with gates, for all large enough . Then .

 

In other words, either randomness is useless for power-time computation, or else circuits can speed up exponential-time uniform computation!

 

2.6 Inclusion extend “upwards,” separations downwards

To develop intuition about complexity, we now discuss a general technique known as padding. In short, the technique shows that if you can trade resource for , then you can also trade a lot of for a lot of . For a metaphor, if you have a magical device that can turn one pound of sill into gold, you can also use it to turn two pounds of sill into gold. The contrapositive is that if you can’t trade a lot of for a lot of , then you also can’t trade a little of for a little of .

We give a first example using the classes that we have encountered so far.

Example 2.3. Suppose that . Then .

 

 

Proof. Let be a function in . Consider the function that on input of length equals computed on the first bits of . Thus, inputs to are padded with useless symbols.

Note that , since in linear time we can erase the last symbols and then just run the algorithm for which takes time quadratic in which is linear in . (If computing square roots is not an available instruction, one can show that computing can be done in linear time, for example using binary search.)

By assumption, .

To compute in time we can then do the following. Given input of length , pad to an input of length in time . Then run the algorithm for . This will take time . QED

 

 

2.7 Problems

Problem 2.1. [Indexing] Describe a TM that on input outputs bit of in time .

 

Problem 2.2. Show that Palindromes can be solved in time on a randomized TM. (Yes, only one tape.)

Hint: View the input as coefficients of polynomials.

 

Problem 2.3. Give a function that is in

 

 

References

 

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

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

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

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

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

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

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

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

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

 

Mathematics of the impossible: Computational Complexity

I am teaching and writing some notes on complexity. I hope they will become a book, so they are organized as such. The notes will be serialized on this blog, and you can find the latest version of the book in pdf here, which has a better rendering of tables, pictures, comic strips, etc.

---

0.1 Conventions, choices, and caveats

I write this section before the work is complete, so some of it may change.

This book covers basic results in complexity theory and can be used for a course on the subject. At the same time, it is perhaps sui generis in that it also tells a story of the quest for impossibility results, includes some personal reflections, and makes some non-standard choices about topics and technical details. Some of this is discussed next.

To test your understanding of the material…

this book is interspersed with mistakes, some subtle, some blatant, some not even mistakes but worrying glimpses into the author’s mind. Please send all bug reports and comments to (my five-letter last name)@ccs.neu.edu to be included in the list of heroes.

The notation.

The mathematical symbol has a special meaning in this text. Every occurrence of denotes a real number . There exist choices for these numbers such that the claims in this book are (or are meant to be) correct. This replaces, is more compact than, and is less prone to abuse than the big-Oh notation (sloppiness hides inside brackets).

Example 0.1. “For all sufficiently large ” can be written as .

“For every and all sufficiently large ” can be written as .

The following are correct statements:

“It is an open problem to show that some function in NP requires circuits of size .” At the moment of this writing, one can replace this occurrence with . Note such a claim will remain true if someone proves a lower bounds. One just needs to “recompile” the constants in this book.

“”, e.g. assign to the first occurrence, to the second.

“”, for="" all="" large="" enough="" .="" assign="" c="16$."

The following are not true:

“ for every ”. No matter what we assign to, we can pick a large enough . Note the assignment to is absolute, independent of .

More generally, when subscripted this notation indicates a function of the subscript. There exist choices for these functions such that the claims in this book are (or are meant to be) correct. Again, each occurrence can indicate a different function.

For the reader who prefers the big-Oh notation a quick an dirty fix is to replace every occurrence of in this book with .

The alphabet of TMs.

I define TMs with a fixed alphabet. This choice slightly simplifies the exposition (one parameter vs. two), while being more in line with common experience (it is more common experience to increase the length of a program than its alphabet). This choice affects the proof of Theorem ??. But it isn’t clear that the details are any worse.

Partial vs. total functions (a.k.a. on promise problems).

Recall that promise problems offer the most direct way of formulating natural computational problems. […] In spite of the foregoing opinions, we adopt the convention of focusing on standard decision and search problems. [2]

I define complexity w.r.t. partial functions whereas most texts consider total functions, i.e. we consider computing functions with arbitrary domains rather than any possible string. This is sometimes called “promise problems.” This affects many things, for example the hierarchy for (Exercise ??).

References and names.

I decided to keep references in the main text to a minimum, just to avoid having a long list later with items “Result X is due to Y,” but relegate discussion to bibliographic notes. I have also decided to not spell out names of authors, which is increasingly awkward. Central results, such as the PCP theorem, are co-authored by five or more people.

Polynomial.

It is customary in complexity theory to bound quantities by a polynomial, as in polynomial time, when in fact the only terms that matters is the leading time. This also lends itself to confusion since polynomials with many terms are useful for many other things. I use power instead of polynomial, as in power time.

Random-access machines.

“Random access” also leads to strange expressions like “randomized random-access” [1].

Reductions.

Are presented as an implication.

Randomness and circuits.

While randomness and circuits are everywhere in current research, and seem to be on everyone’s mind, they are sometimes still relegated to later chapters, almost as an afterthought. This book starts with them right away, and attempts to weave them through the narrative.

Data structures

Their study, especially negative results, squarely belongs to complexity theory. Yet data structures are strangely omitted in common textbooks. Results on data structures even tend to miss main venues for complexity theory to land instead on more algorithmic venues! We hope this book helps to revert this trend.

Algorithms & Complexity

…are of course two sides of the same coin. The rule of thumb I follow is to present algorithms that are surprising and challenge our intuition of computation, and ideally match lower bounds, even though they may not be immediately deployed.

Exercises and problems.

Exercises are interspersed within the narrative and serve as “concept check.” They are not meant to be difficult or new, though some are. Problems are collected at the end and tend to be harder and more original, though some are not.

Summary of some terminological and not choices.

Here it is:

Some other sources	this book	acronym
,
Turing machine	tape machine	TM
random-access machine	rapid-access machine	RAM
polynomial time	power time	P
mapping reduction (sometimes)	reduces to in means
Extended Church-Turing thesis	Power-time computability thesis
pairwise independent	pairwise uniform
FP, promise-P	P
TM with any alphabet	TM with fixed alphabet
classes have total functions	classes have partial functions

Copyright 2022-present by Emanuele Viola

Chapter 1
A teaser

Consider a computer with three bits of memory. There’s also a clock, beating In one clock cycle the computer can read one bit of the input and update its memory arbitrarily based on the value of the bit and the current memory, or stop and return a value.

Let’s give a few examples of what such computer can do.

First, it can compute the function on bits:

If return 0

We didn’t really use the memory. Let’s consider a slightly more complicated example. A word is palindrome if it reads the same both ways, like racecar, non, anna, and so on. Similarly, example of palindrome bit strings are , and so on.

Let’s show that the computer can decide if a given string is palindrome quickly, in steps

and write it in memory bit

If return 0

That was easy. Now consider the function on bits, which is iff the sum of the input bits is and otherwise. Majority, like any other function on bits, can be computed on such a computer in time exponential in . To do that, you do a pass on the input and check if it’s all zero, using the program for And given above. If it is, return . If it is not, you do another pass now checking if it’s all zero except the last bit is . If it is, return . You continue this way until you exhausted all the possible inputs with Majority equals to . If you never returned you can now safely return .

As we said, this works for any function, but it’s terribly inefficient. Can we do better for Majority? Can we compute it in time which is just a power of ?

Exercise 1.1. Convince yourself that this is impossible. Hint: If you start counting bits, you’ll soon run out of memory.

If you solved the exercise, you are not alone.

And yet, we will see the following shocking result:

Shocking theorem:

Majority can be computed on such a computer in time .

And this is not a trick tailored to majority. Many other problems, apparently much more complicated, can also be solved in the same time.

But, there’s something possibly even more shocking.

Shocking situation:

It is consistent with our state of knowledge that every “textbook algorithm” can be solved in time on such a computer! Nobody can disprove that. (Textbook algorithms include sorting, maxflow, dynamic programming algorithms like longest common subsequence etc., graph problems, numerical problems, etc.)

The Shocking theorem gives some explanation for the Shocking situation. It will be hard to rule out efficient programs on this model, since they are so powerful and counterintuitive. In fact, we will see later that this can be formalized. Basically, we will show that the model is so strong that it can compute functions that provably escape the reach of current mathematics… if you believe certain things, like that it’s hard to factor numbers. This now enters some of the mysticism that surrounds complexity theory, where different beliefs and conjectures are pitted against each other in a battle for ground truth.

References

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

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

Postdoc at Northeastern

Apply here. Exciting opportunity. Two years, and you can also write grants. All areas are being considered.

|Northeastern – Simons Institute| < 10, EXP, and PhD in complexity theory

Northeastern recently merged with Mills College, in Oakland, California. The massive campus is less than 10 miles from the Simons Institute for the Theory of Computing. This is the n+1 growth in an amazing streak, including multiple campuses all over the world, naming gifts, and new buildings, including one named after a complexity class: EXP.

This expansion puts Northeastern at the center of the two main hubs for theory in the U.S., the Bay State and the Bay Area.

If you want to work on theory apply to join our theory group. I always have room for strong students.

Correlation bounds against polynomials, a survey

I have updated my survey on correlation bounds against polynomials (actually the new text does not completely subsume the old one). It is available here and comments are (always) welcome. A new result in the survey is that symmetric functions have correlation at least about with polynomials of degree .

Getting started with OpenGL and C++

Below is a template that shows a fractal plant that you can modify with the keys z,w,s. Getting this to work was not straightforward, but the idea is that now you can just have fun and start your videogame. The code is not meant to be optimized at all, but simple. It’s pretty much self-explanatory, basically you can just replace the call to drawFrac in display to show whatever you want, and you handle key strokes in the idle function. I only tested it on Linux.

/*
This is a template to get started with OpenGL (which needs to be installed)
To compile: g++ GLtemplate.c++ -o GLtemplate -lglut -lGLU -lGL
To run: ./GLtemplate

It shows a fractal plant that you can modify with the keys z,w,s

*/

#include <GL/glut.h>
#include <stdio.h>
#include <math.h>

GLfloat userAngle = M_PI/2, userLength = 0.5;

//Keyboard code.  keyStates[x] is true if x is pressed.

bool keyStates[256];     //Key state values

void keyPressed (unsigned char key, int x, int y) { keyStates[key] = true;  }
void keyUp      (unsigned char key, int x, int y) { keyStates[key] = false; }

void idle() {
  if (keyStates['z']) {userAngle += 0.01;}
  if (keyStates['w']) {userLength += 0.01;}
  if (keyStates['s']) {userLength -= 0.01; if (userLength < 0) userLength = 0;}
}

/* Draws a plant from x,y with first piece length l, and angle a
The window has coordinates from (-1,-1) to (1,1).  The center is 0,0.
*/

void drawFrac(GLfloat x,GLfloat y,GLfloat l, GLfloat a) {
  if ( l < 0.001 )
    return;

  glColor3f(0, l*30, 0);
  glLineWidth(l*10);  //Must be before glBegin(GL_LINES)

  glBegin(GL_LINES);

  glVertex2d(x,y);
  glVertex2d(x+cos(a)*l,y+sin(a)*l);

  glEnd();

  drawFrac(x+cos(a)*l*0.3,y+sin(a)*l*0.3,l*0.3,a+M_PI/4);
  drawFrac(x+cos(a)*l*0.6,y+sin(a)*l*0.6,l*0.4,a-M_PI/4);

  drawFrac(x+cos(a)*l,y+sin(a)*l,l*0.5,a+M_PI/4);
  drawFrac(x+cos(a)*l,y+sin(a)*l,l*0.5,a-M_PI/4);
}

//This is the function that draws everything on the screen
void display() {
  glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); //Clear screen

  /* Draw whatever you need here */
  drawFrac(0,0,userLength,userAngle);

  glutSwapBuffers();
  glutPostRedisplay();
}

int main(int argc, char** argv)
{
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE);
    glutInitWindowSize(1000, 1000);
    glutInitWindowPosition(0,0);
    glutCreateWindow("GLtemplate");
    glutDisplayFunc(display);
    glutIdleFunc(idle);
    glutKeyboardUpFunc(keyUp);
    glutKeyboardFunc(keyPressed);

    glutMainLoop();
    return 0;
}

Myth creation: The switching lemma

The history of science is littered with anecdotes about misplaced credit. Because it does not matter if it was A or B who did it; it only matters if it was I or not I. In this spirit I am starting a series of posts about such misplaced credit, which I hesitated before calling more colorfully “myth creation.” Before starting, I want to make absolutely clear that I am in no way criticizing the works themselves or their authors. In fact, many are among my favorites. Moreover, at least in the examples I have in mind right now, the authors do place their work in the appropriate context with the use of citations etc. My only point is the credit that the work has received within and without our community (typically due to inertia and snowball effects rather than anything else).

Of course, at some level this doesn’t matter. You can call Chebichev’s polynomials rainbow sprinkles and the math doesn’t change. And yet at some other level maybe it does matter a little, for science isn’t yet a purely robotic activity. With these posts I will advertise unpopular points of views that might be useful, for example to researchers who are junior or from different communities.

The switching lemma

I must admit I had a good run — Johan Hastad (privately to the blogger)

Random restrictions have been used in complexity theory since at least the 60’s [Sub61]. The first dramatic use in the context of AC0 is due to [FSS84, Ajt83]. These works proved a switching lemma the amazing fact that a DNF gets simplified by a random restriction to the point that it can be written as a CNF, so you can collapse layers and induct. (An exposition is given below.) Using it, they proved super-polynomial lower bounds for AC0. The proof in [FSS84] is very nice, and if I want to get a quick intuition of why switching is at all possible, I often go back to it. [Ajt83] is also a brilliant paper, and long, unavailable online for free, filled with a logical notation which makes some people twitch. The first symbol of the title says it all, and may be the most obscene ever chosen:

Subsequently, [Yao85] proved exponential lower bounds of the form , with a refined analysis of the switching lemma. The bounds are tight, except for the constant which depends on the depth of the circuit. Finally, the star of this post [Has86, Has87] obtained .

Yao’s paper doesn’t quite state that a DNF can be written exactly as a CNF, but it states that it can be approximated. Hastad’s work is the first to prove that a DNF can be written as a CNF, and in this sense his statement is cleaner than Yao’s. However, Yao’s paper states explicitly that a small circuit, after being hit by a restriction, can be set to constant by fixing few more bits.

The modern formulation of the switching lemma says that a DNF can be written as a shallow decision tree (and hence a small CNF). This formulation in terms of decision trees is actually not explicit in Hastad’s work. Beame, in his primer [Bea94], credits Cai with this idea and mentions several researchers noted Hastad’s proof works in this way.

Another switching lemma trivia is that the proof in Hastad’s thesis is actually due to Boppana; Hastad’s original argument — of which apparently no written record exists — was closer to Razborov’s later proof.

So, let’s recap. Random restrictions are already in [Sub61]. The idea of switching is already in [FSS84, Ajt83]. You already had three analyses of these ideas, two giving superpolynomial lower bounds and one [Yao85] giving exponential. The formulation in terms of decision trees isn’t in [Has87], and the proof that appears in [Has87] is due to Boppana.

Still, I would guess [Has87] is more well known than all the other works above combined. [Yao85] did have a following at the time — I think it appeared in the pop news. But hey — have you ever heard of Yao’s switching lemma?

The current citation counts offer mixed support for my thesis:

FSS: 1351

Y: 732

H – paper “Almost optimal…:” 867

H – thesis: 582

But it is very hard to use citation information. The two H citations overlap, and papers are cited for various reasons. For example FSS got a ton of citations for the connection to oracles (which has nothing to do with switching lemmas).

Instead it’s instructive to note the type of citations that you can find in the literature:

Hastad’s switching lemma is a cornerstone of circuit complexity [No mention of FSS, A, Y]

Hastad‘s Switching Lemma is one of the gems of computational complexity [Notes below in passing it builds on FSS, A, Y]

The wikipedia entry is also telling:

In computational complexity theory, Hastad’s switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits. Using the switching lemma, Johan Hastad (1987) showed that... [No mention of FSS,A,Y]

I think that 99% of the contribution of this line of research is the amazing idea that random restrictions simplify a DNF so that you can write it as a CNF and collapse. 90% of the rest is analyzing this to get superpolynomial lower bounds. And 90% of whatever is left is analyzing this to get exponential lower bounds.

Going back to something I mentioned at the beginning, I want to emphasize that Hastad during talks makes a point of reminding the audience that the idea of random restrictions is due to Sipser, and of Boppana’s contribution. And I also would like to thank him for his help with this post.

OK — so maybe this is so, but it must then be the case that [Has87] is the final word on this stuff, like the ultimate tightest analysis that kills the problem. Actually, it is not tight in some regimes of interest, and several cool works of past and recent times address that. In the end, I can only think of one reason why [Has87] entered the mythology in ways that other works did not, the reason that I carefully sidestepped while composing this post: å.

Perhaps one reason behind the aura of the switching lemma is that it’s hard to find examples. It would be nice to read: If you have this extreme DNF here’s what happens, on the other hand for this other extreme DNF here’s what happens, and in general this always works and here’s the switching lemma. Examples are forever – Erdos. Instead the switching lemma is typically presented as blam!: an example-free encoding argument which feels deus ex machina, as in this crisp presentation by Thapen. For a little more discussion, I liked Bogdanov’s lecture notes. Next I give a slightly different exposition of the encoding argument.

The simplest case: Or of bits.

Here the circuit is simply the Or of bits . This and the next case can be analyzed in more familiar ways, but the benefit of the encoding argument presented next is that it will extend to the general case more easily… arguably. Anyway, it’s also just fun to learn a different argument.

So, let’s take a random restriction with exactly stars. Some of the bits may become , others , and others yet may remain unfixed, i.e., assigned to stars. Those that become you can ignore, while if some become then the whole circuit becomes .

We will show that the number of restrictions for which the restricted circuit requires decision trees of depth is small. To accomplish this, we are going to encode/map such restrictions using/to a restriction… with no stars (that is, just a 0/1 assignment to the variables). The gain is clear: just think of a restriction with zero stars versus a restriction with one star. The latter are more by a factor about the number of variables.

A critical observation is that we only want to encode restrictions for which requires large depth. So does not map any variable to , for else the Or is which has decision trees of depth .

The way we are going to encode is this: Simply replace the stars with ones. To go back, replace the ones with stars. We are using the ones in the encoding to “signal” where the stars are.

Hence, the number of bad restrictions is at most , which is tiny compared to the number of restrictions with stars.

The medium case: Or of functions on disjoint inputs.

Instead of working with DNFs, I will consider a circuit which is the Or of arbitrary functions each on bits. You can immediately get this formulation from the usual one for DNFs, but I still find it a little useful since otherwise you might think there is something special about DNFs. What is special is that you take the Or of the functions, and we will exploit this again shortly.

In this warm-up case, we start with functions on disjoint inputs. So, again, let’s take a random restriction with exactly stars. Some of the functions may become , others , and others yet may remain unfixed. Those that become you can ignore, while if some become then the whole circuit becomes .

As before, we will show that the number of restrictions for which the restricted circuit requires decision trees of depth is small. To accomplish this, we are going to encode/map such restrictions using/to a restriction with just stars, plus a little more information. As we saw already, the gain in reducing the number of stars is clear. In particular, standard calculations show that saving stars reduces the number of restrictions by a factor . The auxiliary information will give us a factor of , leading to the familiar bound .

As before, recall that we only want to encode restrictions for which requires large depth. So no function in is , for else the circuit is and has decision trees of depth . Also, you have stars among inputs to functions that are unfixed (i.e., not even fixed to ), for else again you can compute the function reading less than bits. Because the functions are unfixed, there is a setting for those stars (and possibly a few more stars – that would only help the argument) that make the corresponding functions . We are going to pick precisely that setting in our restriction with stars. This allows us to “signal” which functions had inputs with the stars we are saving (namely, those that are the constant ). To completely recover , we simply add extra information to indicate where the stars were. The saving here is that we only have to say where the stars are among symbols, not .

The general case: Or of functions on any subset of bits.

First, the number of functions does not play a role, so you can think you have functions on any possible subset of bits, where some functions may be constant. The idea is the same, except we have to be slightly more careful because when we set values for the stars in one function we may also affect other functions. The idea is simply to fix one function at the time. Specifically, starting with , consider the first function that’s not made constant by . So the inputs to have some stars. As before, let us replace the stars with constants that make the function equal to the constant 1, and append the extra information that allows us to recover where these stars were in .

We’d like to repeat the argument. Note however we only have guarantees about , not with some stars replaced with constants that make equal to . We also can’t just jump to the 2nd function that’s not constant in , since the “signal” fixing for that might clash with the fixing for the first – this is where the overlap in inputs makes things slightly more involved. Instead, because required decision tree depth at least , we note there have to be some assignments to the stars in the input to so that the resulting, further restricted circuit still requires decision tree depth (else has decision trees of depth ).  We append this assignment to the auxiliary information and we continue the argument using the further restricted circuit.

References

[Ajt83]    Mikl�s Ajtai. -formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1–48, 1983.

[Bea94]   Paul Beame. A switching lemma primer. Technical Report UW-CSE-95-07-01, Department of Computer Science and Engineering, University of Washington, November 1994. Available from http://www.cs.washington.edu/homes/beame/.

[FSS84]   Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13–27, 1984.

[Has86]   Johan H�stad. Almost optimal lower bounds for small depth circuits. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6–20. ACM, 1986.

[H�s87]   Johan H�stad. Computational limitations of small-depth circuits. MIT Press, 1987.

[Sub61]   B. A. Subbotovskaya. Realizations of linear functions by formulas using +, *, -. Soviet Mathematics-Doklady, 2:110–112, 1961.

[Yao85]   Andrew Yao. Separating the polynomial-time hierarchy by oracles. In 26th IEEE Symp. on Foundations of Computer Science (FOCS), pages 1–10, 1985.

Talk in two days on correlation bounds

In two days, this Thursday at 12PM EST, I am giving a talk on Correlation bounds and all that.  The talk is hosted by Igor Oliveira and is open to everybody.  Follow this link to join.

In the talk I will discuss correlation bounds for polynomials, and give full proofs of touch on three recent works of mine:

1. Fourier conjectures, correlation bounds, and Majority (link)
2. On correlation bounds against polynomials, with Peter Ivanov and Liam Pavlovic (link)
3. Fooling polynomials using invariant theory, with Harm Derksen (upcoming)