Skip to main content
2 of 5
deleted 10 characters in body

Simulating nondeterministic RAM with nondeterminstic turing machine

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.