Why every language in np is polynomial time reducible


Discuss the below:

Q: 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.

Solution Preview :

Prepared by a verified Expert
Theory of Computation: Why every language in np is polynomial time reducible
Reference No:- TGS01939445

Now Priced at $20 (50% Discount)

Recommended (93%)

Rated (4.5/5)