# 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? – Dave Clarke May 29 '12 at 6:34

## 1 Answer

You are on the right track. To finish the proof you need to show that

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

for some constant $c$.

• so then c can be a function of k, but not n? – Michael Studebaker May 30 '12 at 5:39
• Correct. As $k$ is constant for a specific $L$, so will be $c$ if selected by a function of $k$. – Mike B. May 30 '12 at 7:31