Are P, NP, PSPACE, and NPSPACE complexity classes?

66 Views Asked by At

In Ullman's Introduction to Automata Theory, Languages and Computation, the union theorem (Theorem 12.15) says

Let ${f_i(n) | i = 1, 2, ...}$ be a recursively enumerable collection of recursive functions. Assume each $i$ and $n$,$f_i(n) <f_{i+1}(n)$. There exists an $S(n)$ such that $$DSPACE(S(n)) = \cup_i DSPACE(f_i(n))$$

i.e. $DSPACE(f_i(n))$'s are complexity classes, so is $\cup_i DSPACE(f_i(n))$, because it can be written as $DSPACE(S(n))$ for some $S(n)$.

I was wondering if the following popular sets are complexity classes?

Can the union theorem apply to them?

$$P := \cup_i DTIME(n^i)$$ $$NP := \cup_i NTIME(n^i)$$, $$PSACE := \cup_i DSPACE(n^i)$$, $$NPSPACE := \cup_i NSPACE(n^i)$$

Thanks.