# Contradiction proof for inequality of P and NP?

I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a compelling reason to accept.

We start off by assuming that $$P=NP$$. Then it yields that $$\mathit{SAT} \in P$$ which itself then follows that $$\mathit{SAT} \in TIME(n^k)$$. As stands, we are able to do reduce every language in $$NP$$ to $$\mathit{SAT}$$. Therefore, $$NP \subseteq TIME(n^k)$$. On the contrary, the time hierarchy theorem states that there should be a language $$A \in TIME(n^{k+1})$$, that's not in $$TIME(n^k)$$. This would lead us to conclude that $$A$$ is in $$P$$, while not in $$NP$$, which is a contradiction to our first assumption. So, we came to the conclusion that $$P \neq NP$$.

Is there something wrong with my proof?

• Please, write something like $\mathit{SAT}$ instead of $SAT$. As Leslie Lamport wrote in his original LaTeX book, the latter stands for S times A times T. Apr 25 '19 at 22:31
• Better yet, use the complexity package and simply write \SAT. (I guess that's not available on this stack, though.) Apr 25 '19 at 22:39
• @Oliphaunt Why not suggest an edit when you can improve the post? Although I must say that here the difference (if any) is a lot more subtle than I'd expect. Apr 26 '19 at 7:29
• @Discretelizard I often do, but it was "too much work" this time (i was / am on mobile). Entering all those \$ and \ is finicky work. I chose to educate instead. (This decision may not have been entirely rational.) Apr 26 '19 at 11:38

Then it yields that $$SAT \in P$$ which itself then follows that $$SAT \in TIME(n^k)$$.

Sure.

As stands, we are able to do reduce every language in $$NP$$ to $$SAT$$. Therefore, $$NP \subseteq TIME(n^k)$$.

No. Polynomial time reductions aren't free. We can say it takes $$O(n^{r(L)})$$ time to reduce language $$L$$ to $$SAT$$, where $$r(L)$$ is the exponent in the polynomial time reduction used. This is where your argument falls apart. There is no finite $$k$$ such that for all $$L \in NP$$ we have $$r(L) < k$$. At least this does not follow from $$P = NP$$ and would be a much stronger statement.

And this stronger statement does indeed conflict with the time hierarchy theorem, which tells us that $$P$$ can not collapse into $$TIME(n^k)$$, let alone all of $$NP$$.

• It's not only the time for the reduction itself. You could reduce to a make larger problem. If I can solve X in O (n^5), and I can reduce a problem in Y in O (n^6) to a O(n^3) sized instance of X, then I need O (n^15) in total. Apr 27 '19 at 11:21
• Amusingly, this argument applies to PTIME-complete problems as well, e.g. HORNSAT, which is solvable in linear time (but not all problems in P are linear time).
– cody
Apr 30 '19 at 19:40

Suppose that $$\mathrm{3SAT}\in\mathrm{NTIME}[n^k]$$. By the nondeterministic version of the time hierarchy theorem, for any $$r$$, there is a problem $$X_r\in\mathrm{NTIME}[n^r]$$ that is not in $$\mathrm{NTIME}[n^{r-1}]$$. This is an unconditional result that doesn't depend on any kind of assumption such as $$\mathrm{P}\neq\mathrm{NP}$$

Choose any $$r>k$$. Suppose we have a deterministic reduction from $$X_r$$ to $$\mathrm{3SAT}$$ that runs in time $$n^t$$. It produces a $$\mathrm{3SAT}$$ instance of size at most $$n^t$$, which can be solved in time at most $$(n^t)^k=n^{tk}$$. By our choice of $$X_r$$, we must have $$tk>r-1$$, so $$t>(r+1)/k$$. This function grows without bound with $$r$$.

This means that there is no bound on how long it can take to reduce an arbitrary $$\mathrm{NP}$$ problem to $$\mathrm{3SAT}$$. Even if $$\mathrm{3SAT}\in \mathrm{P}$$, there's still no bound on how long those reductions can take. So, in particular, even if $$\mathrm{3SAT}\in\mathrm{DTIME}[n^{k'}]$$ for some $$k'$$, we can't conclude that $$\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k'}]$$, or even $$\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k''}]$$ for some $$k''>k'$$.