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

October 2018
M T W T F S S
« Jul    
1234567
891011121314
15161718192021
22232425262728
293031  
Advertisements