0
$\begingroup$

The Time Hierarchy Theorem proves that for time-constructible functions, f(n), g(n), if

f(n)log(f(n)) = o(g(n)),

then DTIME(f(n)) $\subsetneq$ DTIME(g(n))

So, there will be problems solvable in g(n) time, but not in f(n) time.

Now, all polynomials are time constructible functions. And, it is easy to see that

$n^k$log($n^k$) = $n^k$.k.log(n) < $n^{k+1}$

This shows that P, the class of decision problems that take polynomial time, is unbounded in the polynomials it requires. As in, there are decision problems in P which are unsolvable in time $n^{k}$, but solvable in time $n^{k+1}$.

Considering that NP-complete problems are atleast as hard as any problem in P, then does this not show that NP-complete problems must require exponential time? For, if a NP-complete problem does have an algorithm that runs in time $n^k$, then, because of the time hierarchy theorem, it must be weaker than some problems in P, which require $n^{k+1}$, or more time to solve.

$\endgroup$
  • 2
    $\begingroup$ "Considering that NP-complete problems are atleast as hard as any problem in P, then does this not show that NP-complete problems must require exponential time?" No. Some problems may take strictly more than every polynomial time and strictly less than every exponential time, consider for example the times $$\exp\left(\sqrt{n}\right)$$ $\endgroup$ – Did Mar 26 '17 at 9:26
4
$\begingroup$

Considering that NP-complete problems are atleast as hard as any problem in P, then does this not show that NP-complete problems must require exponential time?

When we say that one problem is at least as hard as another we normally mean this in the sense of polynomial-time reduction. This means that we can take an instance of one problem and turn it into an instance of the other, using only polynomially much time. This shows that second problem is at least as hard as the first (because any instance of the first can be transformed into an instance of the second) but only up to a polynomial.

More precisely, the reduction takes a polynomial amount of time, and it can also change the input size by up to a polynomial amount. The degree of these polynomials is not bounded, and so it can be larger than $k$.

$\endgroup$

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.