Lecture Nine(On Sep 24, 2008)

Definition 13   $\mathrm{TIME}(T(n)) = \textrm{Class of languages decidable in time }T(n)$. $\mathrm{SPACE}(T(n)) = \textrm{Class of languages decidable in space }T(n)$ . $\mathbf{P}= \cup_k \mathrm{TIME}(n^k)$. $\mathbf{PSPACE}= \cup_k \mathrm{SPACE}(n^k)$. $\mathbf{EXPTIME}= \cup_k \mathrm{TIME}(2^{n^k})$.

Theorem 9   $\mathbf{PSPACE}\subset \mathbf{EXPTIME}$

Proof. Let $L \in \mathbf{PSPACE}$, let $M$ be a PSPACE machine that decides $L$. GOAL: Construct an EXPTIME machine $N$ that decides $L$.

$N = M$ $M$ has only exp(poly) different configurations. $\qedsymbol$

Theorem 10   If $EXPTIME$ language $L$ is $PSPACE$ then $EXPTIME = PSPACE$

What should be true about $L$? For all $x\in EXPTIME$ , $x\leq_Q L$.

Does EXPTIME have a complete language $L$?