Proof by contradiction

Show the error in the following fallacious "proof" that P  NP. Proof by contradiction. Assume that P = NP. Then SAT  P. So, of some k, SAT  TIME(nk). Because every language in NP is polynomial time reducible to SAT, NP  TIME(nk). Therefore P  TIME(nk). But, by the time hierarchy theorem, TIME(nk+1) contains a language which isn't in TIME(nk), which contradicts P  TIME(nk). Therefore P  NP.

See attached file for full problem description.

© SolutionLibrary Inc. 9836dcf9d7