Return to Question

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

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.

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.

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

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.

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

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.

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

We can simulate nondeterministic RAM on nondeterministic TM , with only logarithmic overhead.

But how can we use nondeterminism to reach such a efficient simulation.

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

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.