2
$\begingroup$

Nondeterminstic RAM is like deterministic RAM with extra instruction “JMAYBE” which nondeterministically jump or continue when executed.

According to this paper: An $O(T \log T)$ reduction from RAM computations to satisfiability I guess that we can simulate nondeterministic RAM on nondeterministic TM , with only logarithmic overhead. But this paper also has an important refrence which i could not find “J. Wiedermann, Deterministic and nondeterministic simmulation of RAM by the Turing machine, (IFIP 1983 Paris)”. My question is , how i can show that:

If a language $A$ is recognized by a nondeterministic RAM $P$ within time $T(n)$ and if $P$ has $l(n)$ logarithmic, then $A$ is recognized by some nondeterministic multitape Turing machine within time $ \log T(n) . T(n)$

The function $l(n)$ is associated with the machine, it denotes the time required to store the number $n$. here we assume $l(n) = \lceil \log |n| \rceil$.

This is my homework and i struggle with this question about one week (at first i learned about RAM model) , but i could not figure out how this simmulation is possible, and also i did not find any thing useful. All i know is , there is a naive simmulation which its overhead is quadratic.

$\endgroup$
2
  • $\begingroup$ I don't understand what is meant by $P$ has $l(n)$ logarithmic. Since this is homework, have you tried asking your instructor for help on how to approach this? $\endgroup$
    – D.W.
    Jun 22 at 20:13
  • $\begingroup$ @D.W. I clearify what i meant by that in edited question. Since i thought maybe there is an obvious point which i missed here, i did not ask him yet. I thought maybe i could get some hints from this community. $\endgroup$ Jun 22 at 22:05

1 Answer 1

1
$\begingroup$

Here is your hint. Imagine that we augment $P$ to record a log of all the random-access reads and writes $P$ does to memory (i.e., for each read, record the address and the value that was read; for each write, record the address and the value that was written), in the order they were done. At the end of the computation, could you efficiently verify whether that log is self-consistent and correct? What would be the running time of an algorithm designed to verify the log?

It's your homework problem, so I won't share the complete solution until after the deadline, but if you ponder this thoughtfully, and then think about how you might apply it, it should help you with your homework problem.

$\endgroup$
4
  • $\begingroup$ I have a question, thinking about recursive solution for formulate the answer , is that a good idea or its better to find another and maybe simpler approach? Because i’m thinking about a recursive solution and there are alot of twists which i have to handle after that and i begining to worry that maybe it is a bad approach, because it should not be that complicated ?! $\endgroup$ Jun 25 at 10:52
  • $\begingroup$ @OmidYaghoubi, It sounds like that is unrelated to my answer. Have you figured out how to answer the questions in my hint? What did you come up with? $\endgroup$
    – D.W.
    Jun 25 at 21:54
  • $\begingroup$ If $P$ augmented by a log of all random-access reads and writes $P$ does to memory (in order), then i have to verify that.So i have to look for writes to an address $a_i$ which does not match to their consecutive reads from the same address: $\dots\# (write,a_i,v_i) \# \dots \# (read,a_i,v_j)$ s.t. $v_i \neq v_j$. Also i have to check that first reads from $a_i$ (No wirtes before) to be value of $0$, because at first all the values are $0$.So i have to remember the values and that takes alot of time (maybe with stack?).i thought that maybe i have to use nondeterminism to verify it efficiently? $\endgroup$ Jun 26 at 15:24
  • $\begingroup$ @OmidYaghoubi, What would be the running time of an algorithm designed to verify the log? Hint: an answer should be something like $O(n)$ or $O(n^2)$ or $O(2^n)$, not "alot of time". Can you think of any way to do it efficiently? If not, I suggest you spend some more time pondering how you might approach that. $\endgroup$
    – D.W.
    Jun 26 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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