The Stack Overflow podcast is back! Listen to an interview with our new CEO.
4 of 4 edited tags

Prove that a boolean function computable in T(n) by a RAM machine is in DTIME(T(n)^2)

The question is exercise 1.9 from Arora-Barak's book Computational Complexity — A Modern Approach:


Define a RAM Turing machine to be a Turing machine that has random access memory. We formalize this as follows: The machine has an infinite array A that is initialized to all blanks. It accesses this array as follows. One of the machine's work tapes is designated as the address tape. Also the machine has two special alphabet symbols denoted by R and W and an additional state we denote by q_access. Whenever the machine enters q_access, if its address tape contains 'i'R (where 'i' denotes the binary representation of i) then the value A[i] is written in the cell next to the R symbol. If its tape contains 'i'Wa (where a is some symbol in the machine's alphabet) then A[i] is set to the value a.

Show that if a Boolean function $f$ is computable within time $T(n)$ (for some time constructible $T$) by a RAM TM, then is is in $\mathrm{DTIME}(T(n)^2)$.


The trivial solution by using an additional tape recording pairs (address,value) turns out to be in $\mathrm{DTIME}(T(n)^3)$, since that tape can be of size $O(T(n)^2)$ with $O(T(n))$ pairs while the address of each pair can be of size $O(T(n))$.