Provar NP é um subconjunto da união de DTIME exponencial

Preciso provar que é um subconjunto da união de para todos os .$\mathsf{NP}$$\mathsf{DTIME}(2^{n^c})$$c > 1$

Seja um problema de linguagem / decisão em \ mathsf {NP} . Em seguida, L pode ser decidido dado um certificado de tamanho polinomial em tempo polinomial com uma máquina de Turing M . Então, enumeramos todos os certificados possíveis de tamanho polinomial. Existem 2 ^ l certificados possíveis para um certificado de comprimento l . Para um certificado de comprimento até n ^ c , existem \ sum_ {l = 0} ^ {n ^ c} 2 ^ l = 2 ^ {n ^ c + 1} - 1 muitos certificados. Cada certificado pode ser decidido em tempo polinomial, portanto, concluímos que cada problema em \ mathsf {NP} pode ser resolvido em \ mathsf {DTIME} (2 ^ {n ^ c} n ^ c) . O que estou fazendo errado?$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)$

Você está no caminho certo. Para finalizar a prova, você precisa mostrar que

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

por alguma constante $c$ .