Answers to the SUGGESTED QUIZ (which is actually a digest) 1. Fixing a specific model of computation and a definition of time complexity for it, what enables showing that DTIME(t1) is strictly contained in DTIME(t2)? That is, what should be the relation between t1 and t2 and aspects of the model, for such a results to hold? 2. Ditto for showing that DTIME(t1) = DTIME(t2), when t1 << t2. A1: Computational devices in this model can emulate in time t2 all possible computing devices (in this model) that run in time t1. A2: There is no computing device (in this model) that has running time $t$ such that $t1 \leq t < t2$; that is, for all but finitely many input lengths if a device runs less than t2(x) steps on input x, then it runs at most t1(x) steps on x. Note that the above extends to any complexity measure that is applied to a natural model of computation. Fixing a computational model, a complexity measure is a function $c:\{0,1\}\times\{0,1\}^*\to\N$ such that (1) $c(M,x) < \infty$ iff $M$ halts on input $x$, and (2) one can decide, given $(M,x,t)$, whether or not $c(M,x)=t$.