Sunday, October 17, 2021

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.


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

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 
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,
 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
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.) 
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!
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, 
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!


  1. typo: R(5) -> R(5,5)

    Good luck, Alexandra!

    1. Fixed.
      I would advise Alexandra to work on P vs NP or Riemann rather than R(5,5). She will learn more from the quest to solve P vs NP or Reimann than R(5,5). But I join you in wishing her luck on whatever math problem she will work on this summer!

  2. Regarding Wantzel, see the very interesting paper by Jesper Lützen, "Why was Wantzel overlooked for a century? The changing importance of an impossibility result" (Historia Mathematica
    Volume 36, Issue 4, November 2009, Pages 374-394). In a nutshell, Lützen thinks that it's because at the time, impossibility results were not regarded as being that interesting.

    Tao's result on the Collatz conjecture is very impressive, but it does not bring us any closer to resolving the actual conjecture.

    In my opinion, one fundamental difficulty with P vs NP is that *arbitrary computations lack structure*. If a difficult math problem is finally solved after decades or centuries, it's almost always because people managed to find hidden structure. The pessimism about Ramsey numbers and the Collatz conjecture stems from the feeling that there isn't any hidden structure to be found. From this point of view, P vs NP is closer to Ramsey and Collatz than to Fermat or Poincare.

    For similar reasons, I am skeptical that geometric complexity theory will lead anywhere; they're essentially betting that there's some structure to be found in an arbitrary computation, and that just seems overly optimistic to me.

    1. AH- the key word in your post argument is ``arbitrary''-- there HAVE been lower bounds on restricted models (decision trees, restricted types of circuits) but perhaps those have structure.

      Even so, maybe one day they (not sure who `they' are) will find the needed structure OR an alternative way of looking at it. The work on Greek3 makes me optimistic in the very long run- it took an entirely new mindset, but they did crack it.

      I found an online copy of the article on Wantzel- it is interesting (might be the starting point for another blog post) and here it is:

    2. One "alternative way of looking at it" that I could imagine happening is something like this. We (collectively) decide that P is too large a class; it contains all kinds of junk that we don't care about. We define a proper subclass P' of P that contains "everything we care about." P' contains enough structure that we are able to separate it from NP. We decide that this separation "essentially resolves" the P vs NP problem, and regard the original P vs NP problem as being the wrong question.

    3. @Timothy, this opinion is quite intriguing, though, substantially boils down again to defining "too much junk" without boiling down something to triviality.
      Why is 2-SAT in P and 3-SAT isn't? Does this include "too much junk"? How would you go about this?

  3. Regarding "H6: Make Physics rigorous", it does seem a bit open ended. Going by what Wikipedia says, there does seem to be work being done in this area.

    Just making physics understandable to mathematicians might be a good goal. For example, there is "Physics for Mathematicians, Mechanics I" by Michael Spivak. (I haven't read it.)

    Regarding Quantum Mechanics, it would help if physicists stopped saying things like "cats can be both alive and dead". Sheldon Goldstein is a mathematician who has helped bring some sense to Quantum Mechanics,

    1. Feynman said that NOBODY understands quantum mechanics. Maybe that would be a better problem- use math to help us UNDERSTAND QM.

    2. In this case, Feynman was wrong. Math can help, but it is not only a math problem. It is an applied math problem. Many people today understand Quantum Mechanics. The odd thing is that so many people resist including the equation that tells you how the particles actually move (that's what "mechanics" means). Even when Feynman said it, there were people who understood Quantum Mechanics.

  4. Most of the times when the shortest path is not within the real solution its obvious why thats the case. If the shortest path is connecting A and B its then ignoring some third point C in the proximity of A and B and
    in the final solution the paths AC and CB are included.
    But way more interesting: most of the time that the shortest path is not within the final solution is when the final solution is a complex n-gon and not a simple one. Thats the same with most other naive tests I did.
    I would actually make the case that if the final solution is a simple n-gon it must be possible to find that solution in polynomial time.
    It is just so much simpler if you can ignore all the complex cases. The challenge then would be to construct the n-gon with the shortest circumference.
    If you include the complex n-gon solutions the big problem is defining the circumference of it in a useful way first of all.
    Actually I am sure if you define it correctly any complex n-gon could be folded out to a convex polygon with the exact same surface area and circumference.
    But so far the definition of a complex polygon has not much todo with folding. Anyway it would be hard (impossible) to tell just with the random points along which path the polygon is folded.
    In short: If 2 paths of the solution intersect its a complex polygon but it could be converted into a simple polygon by folding it along 1 of the paths n² paths.
    So yes I think if you wouldnt have to deal with complex n-gon solutions it would be pretty obvious to be polynomial.
    One other insight that I got is that n does not really define the difficulty of finding a solution.
    You could give me a tsp with a billion n if those points are aligned in circle or square or potentialy any other convex n-gon I could give you the correct solution instantly.
    But now to the big problem. I said I am sure if the final solution to a given tsp of size n is a simple n-gon its easy to find that solution. Thats often the case for small n.
    But I am sure the bigger n the more unlikely it becomes that the solution actually is a simple and not a complex n-gon but never impossible.

    One other thing to mention: Very often for n = 7 to 9 the simple n-gon with the shortest circumference is actually very close to the real solution. I dont see a reason why that would change with higher n.
    So just searching the simple n-gon with the shortest circumference might be a far better approach then the minimum spanning tree heuristic.

    In the end I think its hard to say if math is ready for this problem but it feels like there is still a lot to try even with our understanding of math. But as you said in the article, who has the time?

  5. Did you ever think about additional/imaginary information that might be given by a random tsp? Let's say we have n = 10 and let's say its in the plane.
    Let's assume every point has a certain mass. And let's assume in this system gravity exists.
    Then just by giving 10 random locations for the 10 dots their gravity would define a gravitational effect on the whole plane.
    My question for this would be if it is possible theoreticly that the 10 points would not change their postion
    because they would be pulled together by gravity. Thinking about that I came across 1 obvious solution if the dots were so far from each other that the gravitational effect would be irelevant.
    But then it also wouldnt help with a solution. But I was then thinking that maybe its possible to calculate for these 10 dots a certain mass after their position and distance was randomly decided.
    So that they would always stay at their position despite having a mass and causing gravitation because the effects of every dot would cancel each other.
    Those are just ideas I am not done thinking about that. But I do think there is more information with this problem wating to be observed and used.
    And until we have not considered every posible bit of information for the solution it would be too early to conclude its outside of p.

    The idea for this gravitational effect is simple. If you naively look at a random tsp with 10 dots and start including paths to the solution some seem more logical then others. And this gravitational effect
    would just give more insight on some paths that seem logical but end up not being in the final solution after you checked.

    I ran a lot of different naive ideas on a random tsp with n = 7 to 9. For example I checked how often the shortest of all paths would be in the final solution. And actually it was most of the time included.
    Something like ~495/500 times. If the gravitational (or any other additional point of view) gives insight on why in those 5 cases the shortest path was a bad idea finding the perfect solution every time appears more realistic.
    Instead of just checking the length of the paths and including the shortest you would probably check for the easiest/cheapest path based on gravity and distance.
    Say you would compare traveling from earth to sun to traveling to an asteroid in the opposite direction at 1 AU distance. The journey to the sun has the same distance but would be a lot faster.
    In general to the sun is the better journey. But looking at the distance of those 3 objects its a 50-50 chance which path is better.

  6. All: I have a next-generation bespoke computational platform designed to ferret out patterns which can then drive the mathematics and proof. I purport to have a proof for all Collatz orbits including bounds and understand why Tao's tour De force approach would not ferret out the interplay ofmultple numeric series found in CZ and prime series. My platform also ferreted out a novel prime distribution implying twin prime conjectures are true and validated a geometric-calculus non elliptic proof of FLT explaining why FERMAT thought he had an elegant proof but hit a math wall. Any suggestions Jay Rosenberg

  7. As an "amateur" I threw a few hours on many "tiny easy impossible" problems ...

    Now I honestly ask myself WHY they are so difficult to solve, and using Occam's razor an answer come to mind:

    * according to our "way of reasoning" the proofs are "random"

    ... clearly I don't even know if such a sentence could have any meaning :-)

  8. What if the problem turns out unexpectedly simple?

    1. If P=NP this could happen: some algorithmic trick that ONCE YOU SEE IT you wonder how we all missed it.

      If P NE NP I think this is unlikely--- we have some proofs that certain techniques will not work, and generallly proving something CANNOT be done is hard. And as Timothy Chow said in an earlier comment: the notion of arbitrary computation lacks structure, making it hard.

      Of course, having said that, Alexandra will show P NE NP over the summer and I will look foolish. If I understand the proof, that would be okay with me.

  9. Very nice and informative post.
    Important question left open though: Where can we buy the t-shirt?

    1. It was given out by Boaz Barak to all students in CS121 (Harvard's introductory theory course). Boaz was following a tradition that dates all the way back to ... when Bill Gasarch was Harry Lewis's TF for this course! Anyway, I suppose Boaz would be the source, though I imagine the original lot is all gone.

    2. It was given out by Boaz Barak to all students in CS121 (Harvard's introductory theory course). Boaz was following a tradition that dates all the way back to ... when Bill Gasarch was Harry Lewis's TF for this course! Anyway, I suppose Boaz would be the source, though I imagine the original lot is all gone.