12
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\begingroup$ How do you know the bound on address size? Couldn't my first write be to $2^{2^{T(n)}}$? And if you can bound it to $T(n)$, then the address size is $\log\left(T(n)\right)$, not $T(n)$. $\endgroup$
    – Xodarap
    Commented Jul 10, 2012 at 19:35
  • 1
    $\begingroup$ Since the address should be written in the tape by a $T(n)$-time Turing Machine, the size (i.e. string length) of the address can not exceed $O(T(n))$, the accessible address space is $O(2^{T(n)})$. $\endgroup$
    – c c
    Commented Jul 11, 2012 at 4:59
  • 3
    $\begingroup$ Note that Arora and Barak explicitly ask in their introduction for other not post answers to their questions. See also the policy about homework questions. $\endgroup$
    – Kaveh
    Commented Jul 12, 2012 at 3:17
  • $\begingroup$ Sorry for that. I just study the book by myself and get troubled in that question. I don't know if such $O(T(n)^2)$ simulation really exists or it is just a typo. If you know the answer, please email me in private to [email protected], and I'll then close the question. $\endgroup$
    – c c
    Commented Jul 12, 2012 at 5:56
  • $\begingroup$ You can find more in the first chapter of the handbook of theoretical computer science. $\endgroup$
    – Kaveh
    Commented Sep 16, 2012 at 21:22

1 Answer 1

Reset to default
3
$\begingroup$

You write in the comments:

Since the address should be written in the tape by a $T(n)$-time Turing Machine, the size (i.e. string length) of the address can not exceed $O(T(n))$.

Can you use a similar argument to improve the bounds

[The] 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))$.

you mention in the question? You may need to remember what operations are possible in constant time on the RAM, that is using the precise definition the authors use.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I hope this hint is vague enough to respect the book's authors' wishes but also somewhat helpful. (Heuristic: I would tell a student as much if the problem was given as exercise. Probably not in an exam, though.) $\endgroup$
    – Raphael
    Commented Jul 17, 2012 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.