[הערה] לכל c שנבחר, נתקבל n באוכפה. נתקבל חלקה. וכה האיחוד ואוצה לכהב שהיא שווה ל-P הוכחה: יהי c 1 . נתבונן ב-…

[הערה] לכל c שנבחר, נתקבל n באוכפה. נתקבל חלקה. וכה האיחוד ואוצה לכהב שהיא שווה ל-P הוכחה: יהי $c \ge 1$ . נתבונן ב- d = 2^c . [לפשט התאונה הסם] DTime(n^{2^c}) ⊆ DTime(n^d) ⊆ P לכן $- DTime(n^{2^c}) \subseteq P \subset EXP$ . בפרט$, DTime(n^{2^c}) \ne EXP . \cup_{c\ge1} DTime(n^{n^c})$ נוכיח $EXP \subseteq \cup_{c\ge1} DTime(n^{n^c})$ יהי $c \ge 1 . 2^{n^c} = O(n^{n^c})$ . כי אבור n אספיק גדול זה אתקיים לכן $DTime(2^{n^c}) \subseteq DTime(n^{n^c}) \subseteq \cup_{c\ge1} DTime(n^{n^c})$ אכאן $EXP = \cup_{c\ge1} DTime(2^{n^c}) \subseteq \cup_{c\ge1} DTime(n^{n^c})$ נוכיח $\cup_{c\ge1} DTime(n^{n^c}) \subseteq EXP$ יהי $c \ge 1$ . אתקיים$: n^{n^c} = 2^{n^c·log n} \le 2^{n^{c+1}}$ לכל n∈IN . [אדום] n^c log n ≤ n^c·n = n^{c+1} לכן $n^{n^c} = O(2^{n^{c+1}})$ , ואכאן $DTime(n^{n^c}) \subseteq DTime(2^{n^{c+1}}) \subseteq EXP$ . לכן $\cup_{c\ge1} DTime(n^{n^c}) \subseteq EXP$ אכאן השוויון.