6 Complexity Classes

\begin{array}{r} \begin{array}{c} \P = ⋃_{k \geq 1} TIME (n^{k}) & NP = ⋃_{k \geq 1} NTIME (n^{k}) \\ PSPACE = ⋃_{k \geq 1} SPACE (n^{k}) & NPSPACE = ⋃_{k \geq 1} NSPACE (n^{k}) \end{array} \\ \begin{array}{c} EXP = ⋃_{k \geq 1} TIME (2^{n^{k}}) & LOGSPACE = ⋃_{k \geq 1} SPACE (k \times \log (n)) \end{array} \end{array}

6.1 Hierarchy

LOGSPACE \subseteq \P \subseteq NP \subseteq PSPACE = NPSPACE \subset EXP \subset R \subset R E

Since $LOGSPACE ⊊ PSPACE$ , at least one of those inclusions is strict:

LOGSPACE \subseteq \P, \P \subseteq NP, NP \subseteq PSPACE

It is not yet know which one of those is a strict inclusion.

Theorem. $LOGSPACE \subseteq \P$ . Proof. Let $I \in LOGSPACE$ . There $\exists$ a TM that computes $x \in I$ in $\O (\log \abs x)$ space. $M$ can range through $\O (\abs x \log \abs x # Q # Σ^{\log \abs x})$ configurations. A halting computation cannot cycle on configurations. So M computes in $\O (\abs x^{k})$ for some $k$ .

Theorem. (Savitch) $NPSPACE = PSPACE$ .

Theorem. Hierarchy of time and space. If $f$ is appropriate, then $TIME (f (n)) ⊊ TIME ((f (2 n + 1))^{3})$ , and $SPACE (f (n)) ⊊ SPACE (f (n) \times \log f (n))$ . Corollary. $\P ⊊ EXP$
Proof. $\P \subset EXP$ is obvious because $2^{n}$ grows faster than any polynomial. It is strict because $\P \subseteq TIME (2^{n}) ⊊ TIME ((2^{(2 n + 1)})^{3}) \subseteq TIME (2^{n^{2}})$ . This corollary, together with the fact that $NTIME (f (n)) \subseteq TIME (c^{f (n)})$ lets us conclude that $NP \subseteq EXP$ .

Theorem. Hierarchy 2. Let $f$ be an appropriate measuring function, and $k$ a constant. Then

$SPACE (f (n)) \subseteq NSPACE (f (n))$	$TIME (f (n)) \subseteq NTIME (f (n))$
$NSPACE (f (n)) \subseteq TIME (k^{\log n + f (n)})$

Resulting regular expression:

L_{2} = {y : \exists x, z s . t . | x | = | z | a n d x y z \in L}

(Example) is regular.onsider some DFA for $L$ . For every $n \geq 0$ , let $A_{n}$ be the set of states $s$ such that there is *some* word of length $n$ which leads the DFA from the initial state to $s$ . Let $B_{n}$ be the set of states $t$ such that there is *some* word of length $n$ which leads the DFA from $t$ to an accepting state. Finally, for any two states $s, t$ , let $R_{s, t}$ be the (regular) set of words leading the DFA from $s$ to $t$ . We have

L_{2} = ⋃_{n \geq 0} ⋃_{\begin{matrix} s \in A_{n} \\ t \in B_{n} \end{matrix}} R_{s, t} .

Since there are only finitely many possibilities for $s, t$ , the union is in fact finite, and so regular

6 Complexity Classes

6.1 Hierarchy

Resulting regular expres­sion:

Resulting regular expression: