On the Edge of Eclipses and P=NP

A topical look at Norbert Blum’s paper and wider thoughts.

Cropped from source

Thales of Miletus may—or may not—have accurately predicted one or more total solar eclipses in the years 585 through 581 BCE.

Today we discuss the nature of science viewed from mathematics and computing. A serious claim of by Norbert Blum has shot in front of what we were planning to say about next Monday’s total solar eclipse in the US.

Predicting eclipses is often hailed as an awakening of scientific method, one using mathematics both to infer solar and lunar cycles and for geometrical analysis. The aspects of science that we want to talk about are not “The Scientific Method” as commonly expounded in step-by-step fashion but rather the nature of scientific knowledge and human pursuits of it. We start with an observation drawn from a recent article in the Washington Post.

Despite several thousand years of experience predicting eclipses and our possession of GPS devices able to determine locations to an accuracy of several feet, we still cannot predict the zone of totality any closer than a mile.

The reason is not any fault on Earth but with the Sun: it bellows chaotically and for all we know a swell may nip its surface yea-far above the lunar disk at any time. Keeping open even a sliver of the nuclear furnace changes the character of the experience.

The Post’s article does a public service of telling people living on the edge of the swath not to think it is a sharp OFF/ON like a Boolean circuit gate. People must not always expect total sharpness from science. Happily there is a second point: you don’t have to drive very far to get a generous dose of totality. This is simply because as you move from the edge of a circle toward the center, the left-to-right breadth of the interior grows initially very quickly. This is our metaphor for how science becomes thick and solid quickly after we transit the time of being on its edge.

Incidentally, your GLL folks will be in the state of New York next week, nowhere near the swath. Next time in Buffalo. Also incidentally, Thales is said to be the first person credited with discovering mathematical theorems, namely that a triangle made by a circle’s diameter and another point on the circle is a right triangle and that lengths of certain intersecting line segments are proportional.

Norbert Blum’s Paper

The transit time is our focus on this blog: the experience of doing research amid inspirations and traps and tricks and gleams and uncertainty. Swaths of our community are experiencing another transit right now.

Norbert Blum has claimed a proof that P is not equal to NP. In his pedigree is holding the record for a concrete general Boolean circuit lower bound over the full binary basis for over 30 years—until it was recently nudged from his to His paper passes many filters of seriousness, including his saying how his proof surmounts known barriers. Ken and I want to know what we all want to know: is the proof correct?

More generally, even if the proof is flawed, does it contain new ideas that may be useful in the future? Blum’s proof claims a very strong lower bound of on the circuit complexity of whether a graph of edges has a clique of size . He gets a lower bound of for another function, where the tilde means up to factors of in the exponent. We would be excited if he had even proved that this function has a super-linear Boolean complexity.

Blum’s insight is that the approximation methods used in monotone complexity on the clique function can be generalized to non-monotone complexity. It is launched by technical improvements to these methods in a 1999 paper by Christer Berg and Staffan Ulfberg. This is the very high level of what he tries to do, and is the one thing that we wish to comment on.

The Structure Of The Proof

Looking quickly at the 38 page argument an issue arose in our minds. We thought we would share this issue. It is not a flaw, it is an issue that we think needs to be thought about more expressly.

As we understand his proof it takes a boolean circuit for some monotone function and places it in some topological order. Let this be

So far nothing unreasonable. Note is equal to , of course. Then it seems that he uses an induction on the steps of the computation. Let be the information that he gathers from the first steps. Technically tells us something about the computation so far. The punch line is then that tells us something impossible about which is of course . Wonderful. This implies the claimed lower bound on which solves the question.

The Issue

The trouble with this is the following—we studied this before and it is called the “bait and switch” problem. Let be some random function of polynomial Boolean complexity and let . Then assume that there is a polynomial size circuit for . Clearly there is one for and too. Create a circuit that mixes the computing of and in some random order. Let the last step of the circuit be take and and form , Note this computes .

The key point is this:

No step of the computation along the way has anything obvious to do with . Only at the very last step does appear.

This means intuitively to us that an inductive argument that tries to compute information gate by gate is in trouble. How can the ‘s that the proof compute have any information about during the induction? This is not a “flaw” but it does seem to be a serious issue.

If nothing else we need to understand how the information suddenly at the end unravels and reveals information about . I think this issue is troubling—at least to us. It is important to note that this trick cannot seem to be applied to purely monotone computations, since the last step must be non-monotone—it must compute the function. The old post also notes a relation between the standard circuit complexity and the monotone complexity of a related function .

The Outer Structure of the Proof

While we are grappling with the paper and writing these thoughts we are following an ongoing discussion on StackExchange and in comments to a post by Luca Trevisan, a post by John Baez, and a Hacker News thread, among several other places.

The paper has a relatively short “crunch” in its sections 5 and 6, pages 25–35. These follow a long section 4 describing and honing Berg and Uffberg’s work. What the latter did was show that a kind of circuit approximation obatined via small DNF formulas in Alexander Razborov’s famous lower–bound papers (see also these notes by Tim Gowers) can also be obtained with small CNF formulas. What strikes us is that Blum’s main theorem is literally a meta-theorem referencing this process:

Theorem 6: Let be any monotone Boolean function. Assume that there is a CNF-DNF-approximator which can be used to prove a lower bound for . Then can also be used to prove the same lower bound for .

The nub being discussed now is whether this theorem is “self-defeating” by its own generality. There may be cases of that meet the hypotheses but have polynomial . The StackExchange thread is discussing this for functions of Boolean strings denoting -node -edge graphs that give value whenever the graph is a -clique (with no other edges) and when it is a complete -partite graph. Some such functions related to the theta function of László Lovász (see also “Theorem 1” in this post for context) have polynomial complexity, meet the conditions of Razborov’s method, and don’t appear to obstruct Berg and Uffberg’s construction as used by Blum. But if they go through there, and if Blum’s further constructions using an inductively defined function would go through transparently, then there must be an error.

Inner Issues and Calculating

The details of in section 5 have also been called into question. We are unsure what to say about a claim by Gustav Nordh that carrying out the inductive construction as written yields a false conclusion that the monomial is an implicant of a formula equivalent to . There are also comments about unclarity of neighboring definitions, including this from Shachar Lovett in Luca’s blog since we drafted this section.

But this leads us to a larger point. Both of us are involved right now with painstaking constructions involving quantum circuits and products of permutations that we are programming (in Python). Pages 27–28 of Blum’s paper give a construction that can be programmed. If this is done enough to crank out some examples, then we may verify that potential flaws crop up or alternatively bolster confidence in junctures of the proof so as to focus on others first. This ability is one way we are now empowered to sharpen “fuzzy edges” of our science.

Open Problems

Is the proof correct? Or will it fall into eclipse? We will see shortly no doubt. Comparing this table of eclipses since 2003 and Gerhard Woeginger’s page of claimed proofs over mostly the same time period, we are struck that ‘‘ and ‘‘ claims have been about twice as frequent as lunar and solar eclipses, respectively.

[restored missing links; a few word and format changes]

Modeling Reality

A surprising theorem about differential equations

Composite of src1, src2.

Olivier Bournez and Amaury Pouly have proved an interesting theorem about modeling physical systems. They presented their paper at ICALP 2017 last month in Warsaw.

Today Ken and I wish to explain their theorem and its possible connections to complexity theory.

Maryam Mirzakhani, 1977–2017

Including debt to Marina Ratner, 1938-2017

By joint permission of Assad Binakhahi, artist, and Radio Farda (source)

Maryam Mirzakhani won the Fields Medal in 2014. We and the whole community are grieving after losing her to breast cancer two weeks ago. She made several breakthroughs in the geometric understanding of dynamical systems. Who knows what other great results she would have found if she had lived: we will never know. Besides her research she also was the first woman and the first Iranian to win the Fields Medal.

Today we wish to express both our great sorrow and our appreciation of her work.

Kitchen Tile Catalog Complete

All tessellating convex polygons found

Cropped and combined from src1, src2.

Michaël Rao and Marjorie Rice are linked in this month’s news. Rao has just released a paper (see also slides and code here) completing the catalog of convex polygons that tile the plane. Rice, who passed away on July 2 (obit), had expanded the pentagon catalog from 9 to 13 while working in her kitchen in 1975. Rolf Stein found a fourteenth in 1985 and Casey Mann led a team of programmers to find a fifteenth in 2015. Rao has closed the book at 15.

Today Dick and I hail their accomplishments, which we noted from two articles by Natalie Wolchover in Quanta this past Tuesday. We also emphasize some related problems.

Eric and Mike Turn 60

Birthday workshop at Rutgers last January

Combined from source

Eric Allender and Michael Saks have been leading lights in computing theory for four decades. They have both turned 60 this year. I greatly enjoyed the commemorative workshop held in their honor last January 28–29 at DIMACS on the Rutgers campus.

Today Dick and I salute Eric and Mike on this occasion.

Oded Wins The Knuth Prize

Just announced

Oded Goldreich is one of the top researchers in cryptography, randomness, and complexity theory.

Today Ken and I wish to thank the Knuth Prize Committee for selecting Oded as the winner of the 2017 Knuth Prize.

TOC In The Future

Results of the panel at the Theory Fest

Géraud Sénizergues proved in 1997 that equivalence of deterministic pushdown automata (DPDAs) is decidable. Solving this decades-open problem won him the 2002 Gödel Prize.

Today Ken and I want to ponder how theory of computing (TOC) has changed over the years and where it is headed.

Of course we have some idea of how it has changed over the years, since we both have worked in TOC for decades, but the future is a bit more difficult to tell. Actually the future is also safer: people may feel left out and disagree about the past, but the future is yet to happen so who could be left out?