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$ Commented 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$ Commented 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.
    Commented May 30, 2012 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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