6 Complexity Classes

\begin{equation*} \begin{aligned} \begin{matrix} \P = \bigcup _{k\geq 1} \mathrm{TIME}(n^k) & \quad & \mathcal{NP}= \bigcup _{k\geq 1} \mathrm{NTIME}(n^k) \\ \mathrm{PSPACE}= \bigcup _{k\geq 1} \mathrm{SPACE}(n^k) & \quad & \mathrm{NPSPACE}= \bigcup _{k\geq 1} \mathrm{NSPACE}(n^k) \end{matrix}\\ \begin{matrix} \mathrm{EXP}= \bigcup _{k\geq 1} \mathrm{TIME}(2^{n^k}) & \mathrm{LOGSPACE}= \bigcup _{k\geq 1} \mathrm{SPACE}(k \times \log (n)) \end{matrix}\end{aligned}\end{equation*}

6.1 Hierarchy

\[ \mathrm{LOGSPACE}\subseteq \P \subseteq \mathcal{NP}\subseteq \mathrm{PSPACE}= \mathrm{NPSPACE}\subset \mathrm{EXP}\subset R \subset RE \]

Since \(\mathrm{LOGSPACE}\subsetneq \mathrm{PSPACE}\), at least one of those inclusions is strict:

\[ \mathrm{LOGSPACE}\subseteq \P , \P \subseteq \mathcal{NP}, \mathcal{NP}\subseteq \mathrm{PSPACE} \]

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

Theorem. \(\mathrm{LOGSPACE}\subseteq \P \). Proof. Let \(I \in \mathrm{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 \# \Sigma ^{\log \abs {x}})\) configurations. A halting computation cannot cycle on configurations. So M computes in \(\O (\abs {x}^k)\) for some \(k\).

Theorem. (Savitch) \(\mathrm{NPSPACE}= \mathrm{PSPACE}\).

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

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

\(\mathrm{SPACE}(f(n)) \subseteq \mathrm{NSPACE}(f(n))\)

\(\mathrm{TIME}(f(n)) \subseteq \mathrm{NTIME}(f(n))\)

\(\mathrm{NSPACE}(f(n)) \subseteq \mathrm{TIME}(k^{\log n + f(n)})\)

 


Resulting regular expres­sion:

\[ L_2 = \{ y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \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 = \bigcup _{n \geq 0} \bigcup _{\substack {s \in A_n \\ t \in B_n}} R_{s,t}. \]

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