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.

Improve this question
$\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. ♦
    Commented Jun 22, 2022 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$
    – Omid Yaghoubi
    Commented Jun 22, 2022 at 22:05

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Omid Yaghoubi
    Commented Jun 25, 2022 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. ♦
    Commented Jun 25, 2022 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$
    – Omid Yaghoubi
    Commented Jun 26, 2022 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. ♦
    Commented Jun 26, 2022 at 16:26

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.