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?

  • 2
    $\begingroup$ Did you know that you can render your formulas using LaTeX? $\endgroup$ – Dave Clarke May 29 '12 at 6:34

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.