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

May 2018
M T W T F S S
« Jul    
 123456
78910111213
14151617181920
21222324252627
28293031  
Advertisements