P vs. NP: a proof by contradiction from an assumption

Question

Can someone explain to me this proof by contradiction?

Answer 1

As a notational point, I'll use $\mathsf{P}$-superscripts for levels of the polynomial hierarchy (e.g. "$\Sigma^\mathsf{P}_2$," etc.). The notation "$\Sigma_k$" is also used, but that clashes with the notation for the completely different arithmetical hierarchy.

---

The key point is that if $\mathsf{P}=\mathsf{NP}$ then the polynomial hierarchy collapses a lot: everything in the polynomial hierarchy is in fact in $\mathsf{P}$. (See e.g. Theorem $3$ here.)

With this in hand we can argue at first as follows:

• Suppose that some $c$ as in the hypothesis of the theorem exists, and additionally (towards a contradiction) that $\mathsf{P}=\mathsf{NP}$.

• Applying Ravi's theorem and noting that $\Sigma^P_2\subseteq \mathsf{P}$ (since $\mathsf{P}=\mathsf{NP}$) we have that for any $d$ there is some $S_d\in\mathsf{P}$ requiring circuits of size $n^d$.

• But now consider any $d>c$ ...