# Proving NP is a subset of the union of exponential DTIME

I need to prove that $\mathsf{NP}$ is a subset of the union of $\mathsf{DTIME}(2^{n^c})$ for all $c > 1$.

Let $L$ be a language/decision problem in $\mathsf{NP}$. Then $L$ can be decided given a polynomial-size certificate in polynomial time with a turing machine $M$. So then we enumerate all possible certificates of polynomial size. There are $2^l$ possible certificates for a certificate of length $l$. For a certificate of length up to $n^c$, there are $\sum_{l=0}^{n^c} 2^l = 2^{n^c + 1} - 1$ many certificates. Each certificate can be decided in polynomial time, so we get that each problem in $\mathsf{NP}$ can be done in $\mathsf{DTIME}(2^{n^c}n^c)$. What am I doing wrong?

• Did you know that you can render your formulas using LaTeX? May 29, 2012 at 6:34

$\qquad \displaystyle \mathsf{DTIME}(2^{n^k} n^k) \subseteq \mathsf{DTIME}(2^{n^c})$
for some constant $c$.
• Correct. As $k$ is constant for a specific $L$, so will be $c$ if selected by a function of $k$. May 30, 2012 at 7:31