Artificial intelligent assistant

Improper proof that $P \neq NP$ > 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?

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

xcX3v84RxoQ-4GxG32940ukFUIEgYdPy 866f8e75d533612bbec0ccbcc538cd65