P=NP: Perhaps I Change My Mind

Gödel’s Lost Letter and P=NP 2018-03-12

An old result put a new way (in a now-fixed-up post)

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 Ken and I 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 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:

There was no paper by Albert to cite. In our 1982 final version we included a proof of his theorem:

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

$\displaystyle K \in \mathcal{V}/f \implies K \in \mathcal{S'},$

“where the set of strings ${K}$ is complete in ${\mathcal{L}}$ with respect to an appropriate reducibility.”

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

This proof uses ${\mathsf{EXP} \subseteq \mathsf{P/poly}}$ not only for ${L(M) \in \mathsf{P/poly}}$ but also for ${L_M \in \mathsf{P/poly}}$ . For the latter it suffices to have ${L_M}$ polynomial-time reduce to ${L(M)}$ . This follows so long as ${L(M)}$ is complete for some class to which ${L_M}$ also belongs.

Suppose ${M}$ runs in deterministic time ${t(n)}$ . Then both ${L(M)}$ and ${L_M}$ belong to ${\mathsf{DTIME}[t(n)]}$ , the latter because on input ${\langle x,i,t,z \rangle}$ we can run ${M}$ for ${t \leq t(n)}$ steps. With minimal assumptions on the function ${t}$ , ${\mathsf{DTIME}[t(n)]}$ has complete sets ${L(M)}$ , and then ${L_M \in \mathsf{P/poly}}$ follows from ${L(M) \in \mathsf{P/poly}}$ . So we can state the theorem more generally:

Theorem 1 (toujours Meyer) For any time function ${t(n) \leq 2^{n^{O(1)}}}$ , ${\mathsf{DTIME}[t(n)] \subset \mathsf{P/poly} \implies \mathsf{DTIME}[t(n)] \subseteq \Sigma_2^p}$ .

In fact we would get ${\mathsf{DTIME}[t(n)]}$ into ${\Sigma_2^p \cap \Pi_2^p}$ and even smaller classes but that’s going beyond our simple point.

The Point

Our point comes through if we think of a concrete case like deterministic time ${2^{(\log n)^{O(1)}}}$ , called ${\mathsf{QP}}$ for quasipolynomial time. So we have:

Corollary 2 If ${\mathsf{QP} \subset \mathsf{P/poly}}$ then ${\mathsf{QP} \subseteq \Sigma_2^p}$ .

Now mentally substitute ${\mathsf{QP}}$ for ${\mathsf{EXP}}$ (and ` ${\subseteq}$ ‘ for ` ${=}$ ‘) in the way Karp and I summarized the final implication in our paper:

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

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

The point is that we can also do this for time ${t(n) = n^{\log^* n}}$ and even smaller proper super-classes of ${\mathsf{P}}$ . What follows is:

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

Reflecting…

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

“[I]f someone proved ${\mathsf{P} = \mathsf{NP}}$ , that wouldn’t be a total disaster for lower bounds re-search: at least it would immediately imply ${\mathsf{EXP} \not\subseteq \mathsf{P/poly}}$ (via ${\mathsf{EXP = EXP^{NP^{NP}}}}$ ).”

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

So I’m rethinking my angle on ${\mathsf{P} = \mathsf{NP}}$ . I’ve always propounded that good lower bounds flow like ripples from new upper bounds, but the wake of ${\mathsf{P} = \mathsf{NP}}$ seems a tsunami. We wonder if Bill Gasarch will do a 3rd edition of his famous poll about ${\mathsf{P}}$ versus ${\mathsf{NP}}$ . Ken and I offset each other with our votes last time, but maybe not this time.

We also wonder whether Theorem 1 can be given even stronger statements in ways that are useful. In the original version of this post we overlooked a point noted first by Ryan Williams here and thought we had ${\mathsf{EXP} \cap \mathsf{P/poly} \subseteq \Sigma_2^p}$ . To patch it, call a language ${L}$ in ${\mathsf{EXP}}$ “reflective” if there is a TM ${M}$ running in exponential time such that ${L(M) = L}$ and ${L_M}$ (namely, the “tableau” language defined above) polynomial-time reduces to ${L}$ . The complete sets ${L}$ mentioned above for classes within ${\mathsf{EXP}}$ are reflective. If we let ${\mathsf{EXP}_R}$ denote the subclass of reflective languages, then we can say:

$\displaystyle \mathsf{EXP}_R \cap \mathsf{P/poly} \subseteq \Sigma_2^p.$

Note that per Lance Fortnow’s comment here, sparse languages ${L}$ are candidates for being non-reflective: the tableau language ${L_M}$ which we would wish to polynomial-time Turing reduce to ${L}$ is generally dense.

Open Problems

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

Is the notion of “reflective” known? useful?

[fixed error in original Theorem 1 and surrounding text; added paragraph about it before “Open Problems”; moved query about “cosmological” formulas to a comment.]