What happened to P vs. NP?

The great discovery of computer science in the 1970s was the distinction between P and NP. All problems in P were equivalently tractable, and all problems in NP (assuming P≠NP) were equivalently intractable. And this came with a prediction seemingly beyond doubt: as computers grew faster in the future, the gulf between the two classes would widen.

What ever happened? Forty years on, P vs. NP is famous as a mathematical challenge, a million-dollar Clay problem, and it’s a reference point for all kinds of theoretical analyses; but though computers got millions of times faster, the gulf seems to have narrowed! Nowadays a long list of NP-complete problems are largely tractable in practice, including traveling salesman, maximum cut, edge coloring, frequency assignment, maximum clique, 3SAT, set cover, vertex coloring, knapsack, and integer programming. And only theorists nowadays regard all problems in NP as equivalent.

The explanation seems to have two parts. One is that NP-completeness is defined by worst-case analysis, and many problems turn out to be rarely in that zone, especially if softened up with good heuristics or randomization. 3SAT is one example, now a workhorse of practical computing, and even more striking is that the simplex algorithm is used all the time for linear programming even though it’s an exponential algorithm for a polynomial problem. The other is that NP-completeness is defined by exact optima, whereas if one relaxes the goal by a fraction, what used to be exponential may become polynomial. By such means a discrete problem can often be approximately solved, even in the worst case, via continuous algorithms such as linear or semidefinite programming. An example is max cut.

Nobody seems to talk much about this great surprise at the epicenter of computer science. This puzzles me.

[9 December 2018]

Advertisements

Advice for an applied math talk

1.  Begin with a thorough discussion of your Table of Contents. This will help the audience follow your presentation.

2.  Aim for about three slides per minute. For example, 72 slides is good for a 25-minute talk.

3.  Report error estimates and computer timings to at least six digits of accuracy. For example, it’s more precise to say you got an error of 3.22005e-8 in 5.52723 seconds than 3.2e-8 in 5.5 seconds.

4.  Present numbers, not plots. Plots leave a vague and fuzzy impression.

5.  Be sure to give details of the proofs. A proof without details isn’t rigorous.

6.  Aim the laser at the screen and wave it around the part of the slide you’re talking about. This helps the audience pay attention.

7. As your time slot nears its end, speed up if necessary. Don’t risk failing to cover all your material.

[6 December 2018]

Two views of mathematical functions

The 19th century view was that a function was analytic. Of course, some functions were less smooth than that, but analyticity was the starting assumption.

The 20th century view is that a function is continuous. Of course, some functions are smoother than that, but continuity is the starting assumption. (Have you ever seen a merely continuous function? I think there is one main example: a random Brownian path.)

The 20th century view has utterly taken over among pure mathematicians. One can understand this on the basis that analytic functions are too easy to offer research challenges. Unfortunately, the same view has been copied by the numerical analysts, who ought to have been guided by what applications look like. One sees this in their edifice of results expressed in the language of Sobolev spaces. The point of Sobolev spaces is to make precise distinctions between, say, a function with one derivative and a function with one-and-a-half derivatives. Nineteenth-century mathematicians did not spend their time on such distinctions.

And so it is that numerical analysts prove technical, rigorous theorems about the convergence of algorithms whose convergence is nowhere near optimal for most applied problems. Meanwhile pure mathematics continues its drift away from science.

[1 December 2018]

Flypaper and the Faraday cage

For the first time in my life this summer, I had to buy flypaper. The fruit flies in our kitchen in Lyon were annoying. It became fascinating to watch them dart around seemingly at random, and occasionally light on the sticky paper.

Suppose they fly truly in a path of Brownian motion (in fact it’s not so simple), and suppose I had hung a ring of flypapers (in fact I hung just one). Then this would have been the same mathematics as the Faraday cage! For electric fields are governed by Laplace’s equation, just like Brownian motion.

Our analysis of the Faraday cage translates as follows to fruit flies getting through a ring of flypapers to a banana. (a) As long as there are good-sized gaps between the papers, the number of flies getting through will not be negligible (this was Feynman’s error). (b) If the papers themselves are made narrower, even down to a scale of millimeters, the effectiveness of the cage diminishes only slightly (in proportion to an inverse-logarithm of the radius). This is one of the paradoxes of Brownian paths, going back to Berg and Purcell in 1977.

[24 November 2018]

Fake News

In this awful Trump era we’ve learned that whether people consider something to be true or not may not depend very much on, well, whether it is true or not. Deeper than truth, we have learned, lies allegiance.

But this is not our first disobedience! Wise societies have long accepted that while it is appropriate to reason from facts in other areas, rationality becomes boorish and simplistic when the subject is religion. In that department, one must respect a deeper source of knowledge called “faith”. So long before the current era, we’ve all had plenty of practice with the intellectual dishonesty needed for a world of fake news. Learning to shut off our minds when discussing religion was our original sin as rational citizens, the tasting of the tree of disknowledge.

[28 November 2018]

Macron is more unpopular than Trump

In my year in France, I never once heard anyone speak with enthusiasm about Emmanuel Macron.

For those of you who’ve forgotten the bitterness of late 2018, let me summarize. The leading figure in the world trying to tear down the postwar liberal order is Donald Trump, the most destructive force the world has seen in my lifetime. Against him, the leading figure trying to sustain the postwar liberal order is Emmanuel Macron, the first truly international leader Europe has produced since Angela Merkel.

Yet as of this month, in their home countries, Macron’s popularity ratings are lower than Trump’s (low thirties vs. mid-thirties). “Well you know,” is the typical assessment of educated thoughtful French, “he’s a man of the Right.”

What this means in effect is that rather than stand up for the world we believe in, we prefer to wait for somebody better than Macron to come along, and then we’ll think again. I hope you see that this note is not about the French, but about human nature.

[16 October 2018]

False friends and sunny surprises

Getting deeper into French, for an English speaker, is a rich journey. I knew of the notion of false friends, but I had dimly imagined this was a universal effect to be found between any two languages. But no, the relationship of French and English is special.

First let me record a few false friends I hadn’t noticed before this year. I love the way navigation means sailing, and clairvoyant means seeing clearly, and a comedien is an actor, and apprecier means to assess, and sanitaire means health-related, and acquiescer means to agree. All like the English, yet not.

And let me mention some of the sunny surprises, discoveries that THAT’s where a certain English word came from! Today’s Le Monde reports a couvre-feu — a curfew. The participle aisé is a French word for easy. Represailles gives us reprisals, and effrayé afraid, and ennuyé annoyed, and nuisé noisy. A tailleur is one who cuts and measures, a tailor, and a pair is an equal, a peer, and farouche turns into ferocious. The word dûment puzzled me until I realized that ment here is just the adverbial suffix as usual and can be translated into “ly”. And in a biography of Napoleon I got a kick out of a general who had to se rendre. Surrender!

[15 September 2018]