7
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ Did you know that you can render your formulas using LaTeX? $\endgroup$ May 29, 2012 at 6:34

1 Answer 1

6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ so then c can be a function of k, but not n? $\endgroup$ May 30, 2012 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, 2012 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.