## P=NP: Perhaps I Change My Mind

* 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 and some constructions earlier in the paper. In a preliminary section we wrote that our proofs about classes such as involved showing inclusions

“where the set of strings is complete in with respect to an appropriate reducibility.”

But in this case the proof does not need completeness *for *. 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 not only for but also for . For the latter it suffices to have polynomial-time reduce to . This follows so long as is complete for some class to which also belongs.

Suppose runs in deterministic time . Then both and belong to , the latter because on input we can run for steps. With minimal assumptions on the function , has complete sets , and then follows from . So we can state the theorem more generally:

In fact we would get into 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 , called for *quasipolynomial time*. So we have:

Corollary 2If then .

Now mentally substitute for (and `‘ 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 is:

Corollary 3If then .

The point is that we can also do this for time and even smaller proper super-classes of . What follows is:

Any attempt to prove entails proving strong nonuniform circuit lower bounds on languages that are arbitrarily close to being in .

## Reflecting…

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

“[I]f someone proved , that wouldn’t be a total disaster for lower bounds re-search: at least it would immediately imply (via ).”

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

So I’m rethinking my angle on . I’ve always propounded that good lower bounds flow like ripples from new upper bounds, but the wake of seems a tsunami. We wonder if Bill Gasarch will do a 3rd edition of his famous poll about versus . 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 . To patch it, call a language in “reflective” if there is a TM running in exponential time such that and (namely, the “tableau” language defined above) polynomial-time reduces to . The complete sets mentioned above for classes within are reflective. If we let denote the subclass of reflective languages, then we can say:

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

## Open Problems

Is this realization about and strong circuit lower bounds arbitrarily close to 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.]

## Proving Peano Arithmetic Partially Consistent?

* 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.

Read more…

## A Magic Madison Visit

* 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 -completeness.

Read more…

## Lotfi Zadeh 1921–2017

* 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.

Read more…

## Drama Therapy: A Math Viewpoint

* 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.

Read more…

## Happy Birthday Ken

* It was just Ken’s birthday *

Kenneth Regan’s birthday was just the other day.

I believe I join all in wishing him a wonder unbirthday today. Read more…