Der Nachweis von NP ist eine Teilmenge der Vereinigung von exponentiellem DTIME

Ich muss beweisen, dass eine Teilmenge der Vereinigung von für alle .$\mathsf{NP}$$\mathsf{DTIME}(2^{n^c})$$c > 1$

Sei ein Sprach- / Entscheidungsproblem in . Dann kann mit einer Turingmaschine anhand eines Polynomgrößenzertifikats in Polynomzeit entschieden werden . Dann zählen wir alle möglichen Zertifikate mit Polynomgröße auf. Es gibt mögliche Zertifikate für ein Zertifikat der Länge . Für ein Zertifikat mit einer Länge von bis zu gibt es viele Zertifikate. Jedes Zertifikat kann in Polynomzeit entschieden werden, so dass jedes Problem in in kann . Was mache ich falsch?$L$$\mathsf{NP}$$L$$M$$2^l$$l$$n^c$$\sum_{l=0}^{n^c} 2^l = 2^{n^c + 1} - 1$$\mathsf{NP}$$\mathsf{DTIME}(2^{n^c}n^c)$

Du bist auf dem richtigen Weg. Um den Beweis zu beenden, müssen Sie das zeigen

$\qquad \displaystyle \mathsf{DTIME}(2^{n^k} n^k) \subseteq \mathsf{DTIME}(2^{n^c})$

für eine Konstante .$c$