21.2. Models of Computation

How hard a problem is to solve depends on the operations we are allowed to use in our algorithm. The sorting problem mentioned briefly in the introduction of this appendix is a case in point: There is no algorithm that correctly sorts all inputs in \(o(n \lg n)\) time and uses only comparisons to determine the correct order of the input elements. Either the algorithm uses operations other than comparisons or there must exist an input that forces it to take \(\Omega(n \lg n)\) time. If we want to sort integers and use the integer values themselves as indices into an array, then Counting Sort allows us to sort integers between \(1\) and \(m = O(n)\) in \(O(n)\) time. Radix Sort allows us to extend the range to \(m = O(n^c)\) for any constant \(c\). Bucket Sort allows us to sort even arbitrary numbers in expected \(O(n)\) time, provided they are distributed uniformly over a given interval. All of these faster algorithms inspect the actual values of the numbers to be sorted, something we cannot do using comparisons only.

As another example, as mentioned above, only regular languages can be decided by a DFA. If you want to decide a non-regular language at all, let alone efficiently, you need a machine more powerful than a DFA. The bottom line is that to study whether a problem can be solved at all or whether it can be solved efficiently, we need to agree on what operations our algorithm is allowed to use.

The two most commonly considered models of computation when studying the computational complexity of problems are the Turing Machine and the Random Access Machine (RAM). In the interest of keeping this appendix short, I will not discuss these models in detail here. All you need to know is that:

• The Random Access Machine captures fairly closely the capabilities of actual computers. It supports comparisons, basic arithmetic operations, random access into memory, etc. There are subtle differences that lead to the distinction between different types of Random Access Machines. For example, the exact set of arithmetic operations that are allowed—do we have a square-root function and floor and ceiling functions or not—has a significant impact on the time it takes to solve certain geometric problems. If we assume that the objects the RAM can manipulate in constant time are real numbers (not just floating point numbers of limited precision), then we have to be very careful not to abuse this ability because we can pack an unlimited amount of information into a single real number; by manipulating real numbers in constant time then, we can circumvent many lower bounds.

• Just as a push-down automaton (PDA) is an extension of a finite automaton that equips the finite automaton with a memory of unbounded size in the form of a stack, a Turing Machine is an extension of a push-down automaton that allows access to arbitrary elements in this memory, not just the element on the top of the stack. More precisely, a Turing Machine has a tape that extends infinitely in both directions. The PDA's stack can only grow and shrink at one end. The Turing Machine accesses this tape using a read-write head, which it can move across the cells (memory locations) of the tape. The input of the Turing Machine is stored on the tape and the read-write head is initially positioned at the beginning of the input. In each step, the Turing Machine reads the cell of the tape where the read-write head is currently located. Based on the content of this cell and on its current state, it replaces the cell content with a new symbol in its alphabet, leaves the read-write head where it is or moves it one position to the left or right, and transitions to a new state. It may also decide to stop its computation. When it does, it accepts or rejects the input based on whether the current state is accepting or non-accepting.

• The Random Access Machine is clearly more powerful than the Turing Machine. If we want to access a certain memory location, we can do this in constant time on a Random Access Machine,¹ while it may take quite some time to move the read-write head of the Turing Machine to this memory location. In spite of this difference in memory access cost, we have the following important equivalence between Turing Machines and Random Access Machines:

  Theorem 21.2: A language can be decided in polynomial time by a Random Access Machine if and only if it can be decided in polynomial time by a Turing Machine.

  Thus, when studying which problems can be solved in polynomial time, we can focus on Turing Machines. This is useful because Turing Machines are more primitive than Random Access Machines; they support fewer operations in constant time. This makes them easier to reason about formally.