{\huge P=NP: Perhaps I Change My Mind}

An old result put a new way \vspace{.5in}

Albert Meyer knows circuit lower bounds. He co-authored a paper with the late Larry Stockmeyer that proves that small instances of the decision problem of a certain weak second-order logical theory require Boolean circuits with more gates than there are atoms in the observable universe. The instances almost fit into two Tweets using just the Roman typewriter keys.

Today we discuss a simple but perhaps underlooked connection between P=NP and circuit lower bounds.

Albert recently co-authored, with Eric Lehman of Google and his MIT colleague Tom Leighton, the textbook Mathematics for Computer Science. It looks familiar to us because it uses the same MIT Press fonts and layout package as our quantum computing book. They say the following in their Introduction:

Simply put, a proof is a method of establishing truth. Like beauty, ``truth'' sometimes depends on the eye of the beholder, and it should not be surprising that what constitutes a proof differs among fields.

We would say that the game is not only about making truth evident from a proof but also from the mere way a theorem statement is expressed. This post uses an old result of Albert's as an example.

New Statement of Old Result

Well, any criticism of Albert for how his theorem was stated is really criticism of myself, because Dick Karp and I were the first to state it in a paper. Here is exactly how we wrote it in our STOC 1980 version:

\includegraphics[width=3.5in]{KarpLiptonEXPPpoly.png}

In our 1982 final version we included a proof of Albert's theorem:

\includegraphics[width=4in]{KarpLipton1982.png}

As you can see, our proof---Albert's proof?---used completeness for $latex {\mathsf{EXP}}&fg=000000$ and some constructions earlier in the paper. In a preliminary section we wrote that our proofs about classes $latex {\mathcal{L}}&fg=000000$ such as $latex {\mathsf{EXP}}&fg=000000$ involved showing inclusions

$latex \displaystyle K \in \mathcal{V}/f \implies K \in \mathcal{S'}, &fg=000000$

But in this case the proof does not need completeness. I came up with this realization on Wednesday and Ken found essentially the same proof in these lecture notes by Kristoffer Hansen:

\includegraphics[width=4in]{HansenProof.png}

This is the right proof but still the old theorem statement. This proof does not use completeness or any other property of $latex {\mathsf{EXP}}&fg=000000$---it applies to any language in $latex {L}&fg=000000$ in $latex {\mathsf{EXP}}&fg=000000$ that is also in $latex {\mathsf{P/poly}}&fg=000000$. So what it really proves is:

Theorem 1 (\emph) Meyer} $latex {\mathsf{EXP} \cap \mathsf{P/poly} \subseteq \Sigma_2^p}&fg=000000$.

What's the Difference?

The first thing to note is that the new statement does not use the word ``if.'' It is unconditional. Avi Wigderson gave a talk at the FOCS 1995 workshop for Karp's 60th birthday decrying how many theorems in complexity have the form:

``If pigs can whistle then horses can fly''

---where both the `if' and `then' parts are fantastical. This includes any result of the form, ``if $latex {\mathsf{EXP} \subseteq \mathsf{P/poly}}&fg=000000$ then \dots'' But the wording of Theorem 1 is not like that---it is more like:

``Any pig that happens to whistle can also fly.''

That is, any language $latex {L}&fg=000000$ in $latex {\mathsf{EXP}}&fg=000000$ that happens to belong to $latex {\mathsf{P/poly}}&fg=000000$ also belongs to $latex {\Sigma_2^p}&fg=000000$. In fact it belongs to $latex {\Sigma_2^p \cap \Pi_2^p}&fg=000000$ and even smaller classes but that's going beyond our simple point. We can focus on languages $latex {L}&fg=000000$ that belong subclasses of $latex {\mathsf{EXP}}&fg=000000$ such as $latex {\mathsf{QP} =}&fg=000000$ quasi-polynomial time. Let's make a formal statement:

Corollary 2 $latex {\mathsf{QP} \cap \mathsf{P/poly} \subseteq \Sigma_2^p}&fg=000000$.

What's the point? Well, now mentally substitute $latex {\mathsf{QP}}&fg=000000$ for $latex {\mathsf{EXP}}&fg=000000$ (and `$latex {\subseteq}&fg=000000$' for `$latex {=}&fg=000000$') in the way Karp and I summarized the final implication in our paper:

\includegraphics[width=4in]{KarpLipton1982lastpage.png}

What you get after contraposing and using the hierarchy theorem for $latex {\mathsf{P \neq QP}}&fg=000000$ is:

Corollary 3 If $latex {\mathsf{P = NP}}&fg=000000$ then $latex {\mathsf{QP} \not\subseteq \mathsf{P/poly}}&fg=000000$.

This is another ``if pigs can whistle\dots'' statement but the ``then'' part---which works for time $latex {n^{\log^* n}}&fg=000000$ and even smaller proper super-classes of $latex {\mathsf{P}}&fg=000000$---has a more attention-grabbing consequence:

Any attempt to prove $latex {\mathsf{P=NP}}&fg=000000$ entails proving strong nonuniform circuit lower bounds on languages that are arbitrarily close to being in $latex {\mathsf{P}}&fg=000000$.

Rethinking...

Again in the case of $latex {\mathsf{EXP}}&fg=000000$ this implication too has been variously noted. Scott Aaronson mentions it in one sentence of his recent 121-page survey on the $latex {\mathsf{P}}&fg=000000$ versus $latex {\mathsf{NP}}&fg=000000$ question (p65):

\dots[I]f someone proved $latex {\mathsf{P} = \mathsf{NP}}&fg=000000$, that wouldn't be a total disaster for lower bounds research: at least it would immediately imply $latex {\mathsf{EXP} \not\subseteq \mathsf{P/poly}}&fg=000000$ (via $latex {\mathsf{EXP = EXP^{NP^{NP}}}}&fg=000000$)\dots

Maybe I (Dick) considered this in weighing my thoughts about $latex {\mathsf{P} = \mathsf{NP}}&fg=000000$. But that it applies to $latex {\mathsf{QP}}&fg=000000$ in place of $latex {\mathsf{EXP}}&fg=000000$ gives me pause. This greatly amplifies idle thoughts about the irony of how proving $latex {\mathsf{P} = \mathsf{NP}}&fg=000000$ yields the same type of lower bounds against $latex {\mathsf{P/poly}}&fg=000000$ that are involved in the ``Natural Proofs'' barrier against proving $latex {\mathsf{P} \neq \mathsf{NP}}&fg=000000$. Ryan Williams had to combine many ideas just to separate $latex {\mathsf{NEXP}}&fg=000000$ from nonuniform $latex {\mathsf{ACC}}&fg=000000$---not even getting $latex {\mathsf{EXP}}&fg=000000$ on the left nor $latex {\mathsf{P/poly}}&fg=000000$ on the right. (Incidentally, we note this nice recent MIT profile of Ryan.) So having such lower bounds for $latex {\mathsf{QP}}&fg=000000$ just drop from the sky upon $latex {\mathsf{P} = \mathsf{NP}}&fg=000000$ seems jarring.

So I'm rethinking my angle on $latex {\mathsf{P} = \mathsf{NP}}&fg=000000$. I've always propounded that good lower bounds flow like ripples from new upper bounds, but the wake of $latex {\mathsf{P} = \mathsf{NP}}&fg=000000$ seems a tsunami. We hear Bill Gasarch may be doing a 3rd edition of his famous poll about $latex {\mathsf{P}}&fg=000000$ versus $latex {\mathsf{NP}}&fg=000000$. Ken and I canceled each other out last time, but maybe not this time.

Open Problems

Is this realization about $latex {\mathsf{P} = \mathsf{NP}}&fg=000000$ and strong circuit lower bounds arbitrarily close to $latex {\mathsf{P}}&fg=000000$ really new? Can our readers point us to other discussions of it?

It is fun to play with the wonderfully explicit formulas in Albert's paper with Stockmeyer: If you have positive integers $latex {n,m,r}&fg=000000$ such that

1. $latex {m > r + 4 + \log\log(2^{r+3} + m)}&fg=000000$,
2. $latex {r \geq 21 \geq 2\log_2 m}&fg=000000$, and
3. $latex {n \geq 459 + \lfloor(\log_{10}2)m\rfloor + 11\cdot\lfloor\log_{10} m\rfloor}&fg=000000$,