Is MATH Ready for P=NP? Is Alexandra Fahrenthold Ready for P=NP?

(This post was inspired by Harry Lewis emailing me about his granddaughter.)

Harry Lewis's grand daughter Alexandra Fahrenthold (see both pictures) wants information

on how to claim the Millennial prize, so she will be ready.

This raises the question: How likely is it that Alexandra will resolve P vs NP (or perhaps some other Millennium problem if she wants to rebel against her grandfather)?

And more seriously:

1) Have we made progress on P vs NP? (I think not.)

(By we  I mean the community, not Harry and I or Harry and I and Alexandra,

for which the answer is a more definite NO.)

2) If not then why not?

3) How does this compare historically to other open problems in Math?

We will refer to progress made in solving an open problem, though that is a tricky notion since only after a problem is solved can you look back and say what was progress.  One might also count subcases (e.g., n=4 case of FLT) as progress even if they don't help lead to the final proof. I quote a letter from Harry Lewis to me upon reading a first draft of this post:

The one larger point I would suggest adding is to add my operational definition of progress: Progress is being made on a problem if, when the solution is published, it will cite work being published today. Of course that is “operational” only after the fact. Demillo Lipton Perlis at the end have a nice riff on this. The alchemists thought they were making progress on turning lead to gold but they weren’t, even though we know that was actually a solvable problem. Likewise jumping off of higher and higher buildings was not making progress toward heavier than air flight.

---------------------------------------------------------

1) Have we made progress on P vs NP?

a) I tell my students that we have made progress on ruling out certain techniques.

They laugh at that, at which point I decide to not tell them that my PhD thesis was about that sort of thing (oracles). I could say

Once you know what's not going to work you can concentrate one what is going to work.

But that sounds hollow since very few people are working on techniques that

might work (The Geometric Complexity Program, see here, is the only exception I know of.)

b) Are there any partial results? Ryan Williams showed that SAT (and also counting mod versions of it) cannot be done in time n^c and space n^{o(1)} where c is 2cos(2pi/7) (see here).  That is the only concrete lower bound on SAT that I know of.  Is it progress? Sam Buss and Ryan Williams later showed (see here) that, using current techniques, this cannot be improved. If that inspires new techniques that push it further, that would be great. So it is progress? Hard to know now. 

c) There are some circuit lower bounds. One can debate if this is progress.

It will be a much better informed debate once the problem is solved.

So I would say VERY LITTLE PROGRESS.

------------------------------------------------

2) If not then why not?

a) It's only been open for 50 years. A drop in the mathematical bucket.

Counterargument: 50 years of 20th and 21st century mathematics is A LOT.

b) Sociology: The academic computer science conference-model induces us to get out a paper in time for the next conference deadline, and not think deeply about a problem.  Carl Smith thought that P vs NP would be solved by the son of a member of the communist party in the USSR (when there was a USSR) who did not have the pressure to get tenure and grants and such. He may be right.

Counterargument: there are some (1) mavericks who buck the system, and (2) people like Carl's son-of-a-party-member who are allowed to think deeply for years.

c) It's just dang hard! That's the real question. Paul Erdos said of the Collatz Conjecture:

        Mathematics may not be ready for such problems.

Is that true of P vs NP as well?

----------------------------------

3) History and Philosophy.

(In college I once took the following four courses in one semester: History of Philosophy, Philosophy of History, Philosophy of Philosophy, History of History.)

Let's look at problems that were open and then solved:

a) The Three Greek Problems of Antiquity: Squaring the circle (given a circle, construct a square with the same area), doubling the cube (given a line that is the edge of cube, construct another line that is the edge of a cube with twice the volume), trisecting an angle (given an angle, construct two lines whose angle is 1/3 of the given angle), with a straightedge and compass. (When I first heard of this problem I wondered how knowing what direction was North would help trisect an angle.) Posed in roughly 400BC. Not clear what posed means in this context. Did the ask for a construction OR did they ask for EITHER a construction OR a proof that there wasn't one?

This might be the closest analogy to P vs NP: At the time the problem was stated

 MATHEMATICS WAS NOT READY FOR SUCH PROBLEMS. 

It took lots of new math, a better notation, and a different way of looking at numbers, to show that they  could not be done: Pierre Wantzel--doubling the cube (1837),Pierre Wantzel--trisection (1837), Lindemann-Weierstrass--squaring the circle (1882).

NOTE: Some sources list a fourth problem: constructing every regular polygon. Pierre Watnzel proved, in 1837, that a regular n-gon is constructible iff n is the product of a power of 2 and distinct Fermat  primes. (Why isn't Wantzel better known?) 

b) Fermat's Last Theorem. Given its origin, not quite clear when it was posed but 1640's seems fair. This could not be solved when it was posed (On an episode of Dr. Who they claim that Fermat had a simple proof. Note that Dr. Who is fictional and their PhD (if they has one) is probably not in mathematics.) 

MATHEMATICS WAS NOT READY FOR SUCH PROBLEMS, 

but not as much as the three Greek problems. Very steady progress on it, see  here. One of the real milestone was connecting it to other problems in Math. And then Wiles proved it in the 1990's. While the solution was a surprise when it happened it was not that much of a surprise.

QUESTION: Is P vs NP more similar to Greek3 or to FLT? 

c) Peano Arithmetic (and similar systems) are incomplete. Hilbert's 2nd problem (1900) asked to show the axioms of PA were consistent. Godel (1931) showed this could not be done.  Moreover, there are TRUE statements about numbers that PA cannot prove. I think people mostly thought PA was complete so one of the innovations was to think it was incomplete.  

MATHEMATICS WAS READY FOR SUCH PROBLEMS 

but it took the boldness to think PA was incomplete to solve it.  The math needed was known when Hilbert posed the problem. But of course, how to put it together was still quite a challenge.

d) The Continuum Hypothesis, CH, is that there is no cardinality between N and R. Cantor in 1878 asked for a proof that CH was true. It was Hilbert's first problem in 1900.

When Hilbert posed this problem in 1900

MATHEMATICS WAS NOT QUITE  READY FOR SUCH PROBLEMS.

The math to solve it wasn't quite there, but wasn't so far off (of course, that's in hindsight). Godel's model L (1940) was brilliant, though Lowenhiem-Skolem had constructed models.  A model of set theory that was defined by levels was, I think, though of by Russell (though in a very diff way than L). When Cohen did a model where CH is false (1963) he invented forcing for Set Theory, though forcing had already been used in Recursion theory (The Kleene-Post construction of intermediary Turing degrees.)

e) Hilbert's tenth problem (1900): Find an algorithm that will, given a poly in many variables over Z, determine if it has a solution in Z.

MATHEMATICS WAS ALMOST READY FOR SUCH PROBLEMS.

I turns out that there is no such algorithm. Similar to CH: Once it was thought that it was unsolvable, the proof that it was unsolvable just took a few decades. However, it did need  the definition of computable to be pinned down.  Davis-Putnam-Robinson outlined what was needed in the 1950's,and Matiyasevich finished it in 1970.  While it required just the right combination of ideas, and lots of cleverness, the math needed was known.

CAVEAT: There are many restrictions of H10 that are still open. My favorite: is the following solvable: given k, does x^3 + y^3 + z^3 = k have a solution in Z? (See my blog post on this problem here.) For a survey of what is known about subcases see (1) my paper here, though it is has been argued that I am looking at the wrong subcases (see my blog post on this here), and (2) Bogdan Grechuk's paper here

CAVEAT: Matiyasevich has suggested that Hilbert really meant to ask about equations and solutions over  Q. That problem is still open. If it is unsolvable, that might be proven reasonably soon. If it is solvable, then

MATHEMATICS IS NOT READY FOR SUCH PROBLEMS.

f) The four color theorem. Posed in 1852 by Francis Guthrie, proven in 1976. Haken, Appel, and Koch (more on that last name later) did do some very impressive math to set the problem up, and the computer program to finish it off. When the problem was posed (1852) the computing power was not up to the task. So 

COMPUTER SCIENCE WAS NOT READY FOR SUCH PROBLEMS.

Could the ideas to set it up have been done earlier? Maybe, but not much earlier. The result is often attributed to Haken and Appel, but actually there are two papers, and Koch is an author on the second one. Note that (1) Robertson, Sanders, Seymour, Thomas had a simpler, though still computer proof (1996), and (2) Werner Gonthier formalized the proof inside the Coq proof assistant in 2005.

CAVEAT: An open problem that is hard to state precisely is to come up with a non-computer proof.

CAVEAT: There is a non-computer proof that every planar graph is 4.5-colorable, see my blog post in this here. (No, this is not a joke. If it was I would make if funnier and claim there is a non-computer proof that every planar graph is 4 + 1/e colorable.)

g) Poincare Conjecture. Conjectured in 1904 and solved in 2002. To bad---if it was solved in 2004 it would be exactly 100 years. There was some progress on this all along so I don't know which step was the hard one though probably they were all hard. This one is harder for me to speculate on. When it was solved and Darling wanted to know why it was worth $1,000,000 I told her that it says if something tastes and smells and feels like a sphere, its a sphere. She was unimpressed.  But back to our story:  in hindsight,

MATH WAS READY FOR SUCH PROBLEMS

 since there was steady progress. I think of NOT READY as meaning NO progress, NO plan.

h) The Erdos Distance Problem: Show that for any n points in the plane the number of distinct distances is Omega(n/\sqrt{log n}). Not quite solved, but a big milestone was Gutz and Katz proof of Omega(n/log n). For that result

MATH WAS READY FOR SUCH PROBLEMS

Steady progress:  see the Wikipedia entry here. What's of interest to us is that there was a barrier result of Omega(n^{8/9}) by Ruzsa (apparently unpublished) that said the techniques being used could not do better-- so people, in short order, found new techniques.  Here is hoping that happens with P vs NP.

--------------------------------------------------------------------------------

Let's look at problems that are open and unsolved.

a) Collatz Conjecture (also called the 3x+1 conjecture). I asked

Jeff Lagarias, who is an expert on the problem:

Is it true? When will it be resolved? He said Yes and Never.

I once heard there has been NO progress on this problem, though I later  heard that Terry Tao has made some progress. In any case, not much progress has been made. Maybe Erdos was right.

QUESTION: Why does my spell checker think that Collatz is not a word? 

b) Small Ramsey Numbers. I asked Stanislaw Radziszowski, who is an expert on Small Ramsey Numbers (he has a dynamic survey on small Ramsey numbers here) 

What is R(5)?  When will we know? He said 43 and Never.

Worse than being hard, I don't think any nice math has come out of trying to find R(5,5). Too bad. The coloring that gives the lower bound for R(4) and some (perhaps all) of the R(i,j) where i,j\le 4 can be derived from group theory. YEAH! But then connections to interesting math just... stopped. For now? Forever? Joel Spencer told me this is an example of the law of small numbers: patterns that hold for small numbers stop holding when the numbers get too big. (I've seen other things  called the law of small numbers as well.) 

MATH MAY NEVER BE READY FOR SUCH PROBLEMS 

If no interesting math comes out of the attempt to find the exact values of the Ramsey Numbers, then it is not a good problem. 

Note:  The conversations about Collatz and R(5) were within 10 minutes of each other. Depressing day!

c) The Twin Primes Conjecture. Sieve methods have been used to get partial result. YEAH! Yitang Zhang showed there exists infinite x such that x and x + 70million (something like that are prime. YEAH. Its been gotten down to x, x+246 and with various assumptions x,x+12 or x, x+6). YEAH! but Sieve methods are known to NOT be able to prove the  conjecture. Dang it!

DO NOT KNOW IF MATH IS READY FOR SUCH PROBLEMS.

I think people are kind of stuck here. Much like P vs NP, though at least they have some partial results. By contrast, with regard to P vs NP we don't even have that (unless you count Ryan's lower bound on SAT---maybe you do).

Note: I found that information here which seems to be an Encyclopedia Britannica  website. I would have thought that, with the web and Wikipedia, they would be out of business. Good for them to still be in business! 

d) I am not qualified to write about any of the Millennium prizes except P vs NP (am I even qualified for that?)  so I ask my readers to leave opinions (informed or not) about, for which of them, 

MATH IS NOT READY FOR SUCH PROBLEMS

One of the people who worked on the Riemann Hypothesis said: 

I do not recommend spending half your life on the Riemann Hypothesis. 

That raises a different question: When do you give up? (topic for a different blog post). 

e) I am also not qualified to write about the Hilbert Problems where are still unsolved. Note that some of them are not well enough defined  to ever be resolved (H6: Make Physics rigorous) and some are either solved or unsolved depending on who you ask (H4: Construct ALL metrics where lines are geodesics-- surely, he didn't mean ALL metrics. Probably right, but  stop calling me Shirley!) For a byte more about Hilbert's problems, including a few paragraphs on H4,  see my reviews of two books on them, here. Same as the last item- if you have an opinion (informed or not) about, for which of them that are though to be sort-of open, is math ready for them, leave a comment. 

CODA: Alexandra will be working on Collatz this summer!

Let's wish her luck!