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 Proofsbarrier 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.]

An approach to consistency that could work…

Kurt Gödel is feeling bored. Not quite in our English sense of “bored”: German has a word Weltschmerz meaning “world-weariness.” In Kurt’s case it’s Überweltschmerz. We have tried for over a month to get him to do another interview like several times before, but he keeps saying there’s nothing new to talk about.

Today we want to ask all of you—or at least those of you into logic and complexity—whether we can find something to pep Kurt up. Incidentally, we never call him Kurt.

To give a Hilldale Lecture and learn about fairness and dichotomies

 UB CSE50 anniversary source

Jin-Yi Cai was kind enough to help get me, Dick, invited last month to give the Hilldale Lecture in the Physical Sciences for 2017-2018. These lectures are held at The University of Wisconsin-Madison and are supported by the Hilldale Foundation. The lectures started in 1973-1974, which is about the time I started at Yale University—my first faculty appointment.

Today Ken and I wish to talk about my recent visit, discuss new ideas of algorithmic fairness, and then appreciate something about Jin-Yi’s work on “dichotomies” between polynomial time and ${\mathsf{\#P}}$-completeness.

But fuzzy logic lives on forever

 New York Times obituary source

Lotfi Zadeh had a long and amazing life in academics and the real world. He passed away last month, aged 96.

Today Ken and I try to convey the engineering roots of his work. Then we relate some personal stories.

Two more tragic losses coming before a greater tragedy

 Composite of crops from src1, src2

Michael Cohen and Vladimir Voevodsky were in different stages of their careers. Cohen was a graduate student at MIT and was visiting the Simons Institute in Berkeley. He passed away suddenly a week ago Monday on a day he was scheduled to give a talk. Voevodsky won a Fields Medal in 2002 and was a professor at the Institute for Advanced Study in Princeton. He passed away Saturday, also unexpectedly.

Today we join those grieving both losses.

What is drama therapy?

Kathryn Farley obtained her PhD from Northwestern University in performance studies in 2007. After almost a decade working in that area, she has just started a Master’s program at New York University in a related field called drama therapy (DT).

Today, I thought I would talk about the math aspects of DT.