Question

Describe the error in the following fallacious “proof” that.$\mathbf{P}\ne \mathbf{NP}$Assume that P=NP and obtain a contradiction. If P=NP, then SAT? P and so, for some k,SAT?$\mathbf{TIME}\mathbf{(}{\mathbf{n}}^k\mathbf{)}$Because every language in NP is polynomial time reducible to SAT, you have$\mathbf{NP}\mathbf{\subseteq }\mathbf{TIME}\mathbf{(}{\mathbf{n}}^k\mathbf{)}$

. Therefore,.$\mathbf{P}\subseteq \mathbf{TIME}\mathbf{(}{\mathbf{n}}^k\mathbf{)}$Butby the time hierarchy theorem, TIME(n k+1) contains a language that isn’t in ,$\mathbf{TIME}\mathbf{(}{\mathbf{n}}^k\mathbf{)}$ which contradicts.$\mathbf{P}\subseteq \mathbf{TIME}\mathbf{(}{\mathbf{n}}^k\mathbf{)}$Therefore, $P\ne NP.$

Short answer

First, we need to prove $P\ne NP$ and then we have to check the errors in the deceptive proof.

Step-by-step solution

Deceptively proving thatP≠NP

Consider the following deceptive proof:

1. Suppose that $P=NP$which will result in contradiction.
2. If $P=NP$has given, then for some$k\in N$ and,$SAT\in P$,$SAT\in \text{TIME}\left(n^k\right)$
3. $NP\subseteq TIME\left(n^k\right)$because every language in NP is polynomial time reducible to$SAT$
4. Because of the above assumption,$P\subseteq TIME\left(n^k\right)$
5. Then $TIME\left(n^k\right)⊈TIME\left({n^k}^{-1}\right)$is in contradiction with$P\subseteq TIME\left(n^k\right)$

Finding out the error in the above proof 

In the 3^rd point of the above deceptive proofs i.e.,$NP\subseteq TIME\left(n^k\right)$ because, every language in NP is polynomial time reducible to,$SAT$ the time needed for calculating the reduction is not taken into account. Which is the error in the above proof. So, in order for the proof to be error free the time needed for calculating the reduction must be taken into account.