You are currently browsing the tag archive for the ‘space’ 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

August 2018
M T W T F S S
« Jul    
 12345
6789101112
13141516171819
20212223242526
2728293031  
Advertisements