Improper proof that $P \neq NP$

Question

Describe the error in the following fallacious “proof” that $P \neq NP$ . Assume that $P = NP$ and obtain a contradiction. If $P = NP$, then $SAT \in P$ and so for some $k$, $SAT \in TIME(n^k )$. Because every language in $NP$ is polynomial time reducible to $SAT$, you have $NP \subseteq TIME(n^k )$. Therefore, $P \subseteq TIME(n^k )$. But by the time hierarchy theorem, $TIME(n^{k+1})$ contains a language that isn’t in $TIME(n^k )$, which contradicts $P \subseteq TIME(n^k )$. Therefore, $P \neq NP$

On my eye reasoning is correct except the fact, the author doesn't mention about complexity of reduction to $SAT$ problem, yeah?

Answer 1

Because every language in $NP$ is polynomial time reducible to $SAT$, you have $NP \subseteq TIME(n^k )$.

This is the problem here. If some problem is polynomial-time reducible to $SAT$, that does not mean it is in $TIME(n^k)$. Using the Turing reduction definition, this means that it performs $SAT$ a polynomial number of times and it spends polynomial-time outside of $SAT$. However, if, for example, the problem performs the $SAT$ algorithm $\Theta(n)$ times, then it will be in $TIME(n^{k+1})$, because it is $n$ times $TIME(n^k)$.

Therefore, this sentence is the fallacy since not a language polynomial-time reducible to $SAT$ does not mean it will have the same polynomial power as $SAT$

Answer 2

I believe both answers are wrong.

The reduction to $SAT$ will be called only once. For any input string $w$ you will reduce it to $SAT$ and solve $SAT$ in $O(n^{k})$ time. Therefore, if the reduction takes $O(n^{l})$ time, the whole thing will take $O(n^{l}+n^{k})$ time which will not be in $O(n^{k})$ whenever $l>k$.

Answer 3

Your guess is right. As polynomial time reductions are no necessarily linear time reduction, you cannot get from $SAT\in TIME(n^k)$ that $NP\subseteq TIME(n^k)$. This is because if the reduction runs on $O(n^l)$ time, then the problem (which is reduced to $SAT$) will be solve, in general, in$O(n^{kl})$ time and not just $O(n^k)$ time - recall that in the worst case scenario the reduction will produce instances of $SAT$ of size $O(n^l)$.