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 Multitape machines (MTMs)
2.3 Circuits
2.4 Rapidaccess 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
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 gradeschool 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 nonuniform computation.
Keep in mind these two principles when reading the next models.
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 highlevel 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 .
TMs can compute any function if they have sufficiently many states:
2.1.1 You don’t need much to have it all
How powerful are tape machines? Perhaps surprisingly, they are allpowerful.
Powertime 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 rapidaccess 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 selfcontained 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 nonboolean 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 hardwire 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 .) TMTime 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 leftmost 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 Multitape 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 runtime 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 .
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 2TM 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.
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 (fanin ), an output variable (fanin ), a negation gate (fanin ), an And gate (fanin ), or an Or gate (fanin ). The fanin of a gate is the number of edges pointing to the gate, the fanout is the number of edges pointing away from the gate.
An alternating circuit, abbreviated AltCkt, is a circuit with unbounded fanin 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 nonouput 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 exponentialsize 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.
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 .
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 Rapidaccess 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 constanttime 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 rapidaccess 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 .
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 blowup to simulate RAMs.
There are universal RAMs that can simulate any other RAM with only a constantfactor overhead, unlike the logarithmicfactor 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 cellsize 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.
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 bruteforce 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.
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 2TMs. 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:
 is the zero polynomial.
 for every .
 .
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 multivariate generalization of the fundamental fact that a nonzero univariate polynomial of degree has at most roots. The fundamental fact can be recovered setting and .
To prove the multivariate 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 nonzero 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 powersize 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 errorcorrecting 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 derandomize 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 powertime computation, or else circuits can speed up exponentialtime 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.
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.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.
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. Twotape 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., s242(1):230–265, 1937.
[9] Emanuele Viola. Pseudorandom bits and lower bounds for randomized turing machines. Theory of Computing, 18(10):1–12, 2022.