Satz P echte Teilmenge von EXPTIME

Einfache Sprache

Def. Satz P echte Teilmenge von EXPTIME

P ist eine echte Teilmenge von EXPTIME. Also
$$\mathbf{P}\subset\mathbf{EXPTIME}\;.$$

Beweis: Unter Zuhilfenahme des Zeithierarchiesatz ergibt sich folgende Gleichung:

$$\begin{align}\mathbf{P} &= \bigcup_k\mathbf{TIME}(n^k)&\Huge|\normalsize\text{Def. $\mathbf P$}\\&\subseteq \mathbf{TIME}(n^{\log n})&\Huge|\normalsize\text{?}\\&\subset \mathbf{TIME}(2^n)&\Huge|\normalsize\text{Zeithierarchiesatz}\\&\subseteq \bigcup_k\mathbf{TIME}(2^{n^k})&\Huge|\normalsize\text{?}\\&= \mathbf{EXPTIME}&\Huge|\normalsize\text{Def. $\mathbf{EXPTIME}$}\\\end{align}$$

Home:

Type/Note