You are currently browsing the tag archive for the ‘time’ tag.

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

Pages

July 2018
M T W T F S S
« Jul    
 1
2345678
9101112131415
16171819202122
23242526272829
3031  
Advertisements