Computational Complexity | MCQs

Explanation

• A deterministic Turing machine can simulate a non-deterministic Turing machine without using extra time, but it may require more space.
• This is because a deterministic Turing machine can try all possible branches of a non-deterministic Turing machine in parallel, using more space to store the different branches.