# P $\neq$ NP via Time Hierarchy Theorem?

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.

• "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)$$ – Did Mar 26 '17 at 9:26

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