Hierarchy theorems for deterministic time and space, and for nondeterministic time. Details can be found in Chapter 3 of the Arora-Barak book.

Points to consider:

  • Why is it harder to diagonalize nondeterministic machines
  • How does the efficiency of simulation affect the bounds
Advertisements