P vs NP Most Important Open Math Question?
P vs NP was voted the most important open math question by my senior seminar on “The Big Questions” Math 481, followed by the Riemann Hypothesis, Yang-Mills, and Navier-Stokes. The Poincaré Conjecture, proved by Perelman in 2003, was voted the most important proven theorem. What would you say?
Here are their top ten:
1. P vs NP
2. Riemann Hypothesis
3. Yang-Mills
4. Navier-Stokes
5. Poincaré Conjecture (Perelman)
6. Gödel Incompleteness
7. Fermat’s Last Theorem (Wiles)
8. Kelvin Problem
9. Double Bubble Theorem
10. Hales Sphere Packing
Morgan’s “Big Questions” senior seminar, Williams Math 481, Fall 2008. Ranking the questions was suggested by Ali Barrett ’09, lower left in second photo.
Welcome to my blog. I also have a blog at the
a:
No Twin Primes?
3 December 2008, 12:03 amBrooks Moses:
Coming at this from the perspective of having done rather a lot of computational fluid dynamics and very little theoretical mathematics, I find the presence of “Navier-Stokes” on this list rather incongruous — to me, it’s not an “unsolved math question” so much as a set of partial differential equations. Is the “question” here that of proving whether continuous solutions exist for all continuous boundary conditions?
(I ask in part because there are all sorts of other deeply interesting questions encompassed in that set of equations, though few of them are quite so pure mathematically.)
3 December 2008, 1:23 amFrank Morgan:
Dear Brooks,
3 December 2008, 9:38 amYes, those are the two Million-Dollar Millennium Prize questions: whether solutions to Navier-Stokes exist and are smooth for all nice initial conditions.
Danny Y. Huang:
I find that high-level mathematical questions rather philosophical. That mathematics, in its purest form, is philosophy is not an overstatement. Undoubtedly, we can breathe, eat and live without even having the tiniest connections with Fermat’s Last Theorem; nor are our lives in any way affected if we do not know about supernovae (recent news) or blackholes or quarks or God. But when mathematicians mathematicize just as philosophers philosophize, we are stepping out of our comfort zone; we are leaving the Cave, to see that the world is not simply a bunch of dancing shadows. Who knows what/how Gödel’s Incompleteness Theorem can contribute to the current financial crises or credit crunch. Why would that matter? Thousands of years ago, our ancestors looked into the abyss of the night sky. They saw stars. They asked why. Now we’re talking about P and NPs, DNAs and Relativity. Essentially, we’ve been doing the same thing. We’re looking for something. We don’t know what it is yet. Yet we keep looking. That’s not what makes us mathematicians or philosophers; that’s what makes us human.
5 December 2008, 12:54 amArjun N:
From a purely practical point of view, I think P vs NP. It is so important in making some headway on computational complexity. “Solving” P vs NP will entail making great strides on algorithmic lower bounds – something that is in a very primitive state right now. Apart from saying comparison sort is tight n log n, we really can’t say much.
I would be very shocked if we enter the era of quantum computing (some decades from now, if at all) without getting a lower bound on the NP-complete problems. We know quantum computers can’t bring exponential time problems to polynomial. But otherwise, we don’t know a lot else. All the quantum theoreticians have right now is Shor’s and Grover’s algorithms.
And of course, all hell will break loose if P = NP.
14 December 2008, 1:05 amFrank Morgan:
Date: Tue, 30 Dec 2008 13:58:03 -0500 (EST)
From: [email protected]
Dear Prof. Morgan,
I found an interesting article in the New Scientist [by Ian Stewart].
Hristo
Dear Hristo,
Yes, an interesting variation on sphere packing is to minimize the volume of the convex hull of n unit balls. As Stewart says, apparently for n ≤ 56, it is best to arrange them along a straight line in a “sausage” shape, while for larger n, using the Kepler-Hales sphere packing in large balls does better. The Sausage Conjecture says that starting in dimension 5, the sausage shape always wins, no matter how large n is.
31 December 2008, 9:23 amDavid Pesikoff ('90):
As a former mathematician, I just finished Sautoy’s The Music of the Primes,the story of the search for the solution to the Reimann Hypothesis. It’s quite readable, although I admit the math concerning imaginary numbers and their corresponding map to various mountainous graphs indicating prime numbers was somewhat lost on me. Nonetheless, it’s a good story of human endeavor and the randomness that is part of success. Some of the major advances in solving the problem came about purely by chance as different academic disciplines collided unexpectedly. I suppose what I appreciated most from the book was the nature of math’s relationship to music, physics, philosophy, Greek history, the Industrial Revolution, and religion. And those were just the facets of life touched on by the search for this single problem. Well worth the read.
3 January 2009, 1:56 pmdlp
David Hansen:
This is a lovely list. I think it is worth emphasizing that when a mathematician claims an open problem is important, it is because any technique which would lead to a solution would likely apply to a host of other equally interesting problems. In short, impregnable problems breed powerful tools. For example, Perelman’s Ricci flow constructions have already been applied to a number of other manifold classification problems in differential geometry. A solution to RH would certainly tell us something new about primes, and perhaps a solution to P vs. NP would lead to a host of new and efficient algorithms.
4 January 2009, 6:05 pmDavid Pesikoff '90:
I was emailing Frank with some thoughts following my read of Sautoy’s The Music of the Primes, the story of the search for a solution to the Reimann Hypothesis.
Specifically, I wondered whether when we find the solution to Reimann if it will give us a pattern to the the numerical specifics of π or e. So is there a pattern to the way π and e expand which parallels the way prime numbers occur. I wonder.
6 January 2009, 12:56 pmdlp
David Hansen:
I think it’s fairly widely believed that the digits of π and e are random in just about any sense of the word. On the other hand, algorithms are known which allow one to compute the nth digit of π without knowing the previous digits…
6 January 2009, 5:23 pmFrank Morgan:
Arthur Jaffe, founder of the Clay Institute, told me at the 2009 joint math meetings that he thinks that Yang-Mills is the hardest of the Clay Millennium Problems, partly because you have to prove it for every gauge group.
12 January 2009, 9:48 amDaniel Moskovich:
I’m surprised the four colour theorem didn’t make the list…
4 February 2009, 2:56 amAlso, why does “most important proven mathematical theorem” need to be something hard? I think the fundamental theorem of arithmetic (or the fundamental theorem of calculus) are also important proven mathematical theorems…
Javaid Aslam:
Hello All:
I have a paper, The Collapse of the Polynomial Hierarchy: NP = P
with two versions (short and long posted on arxiv.org as follows:
Short version: http://arxiv.org/pdf/0812.1385v11
Full paper appears on: http://arxiv.org/pdf/0812.1385v9
—————–
The Collapse of the Polynomial Hierarchy: NP = P
We present a novel extension to the permutation group enumeration technique
which is well known to have polynomial time algorithms. This extended technique
allows each perfect matching in a bipartite graph of size O(n) to be expressed
as a unique directed path in a directed acyclic graph of size $O(n^3)$.
Thus it transforms the perfect matching counting problem into a directed path
counting problem.
We further show how this technique can be used for solving a class of
#P-complete counting problems by NC-algorithms, where the solution space of the
associated search problems spans a symmetric group. Two examples of the natural
candidates in this class are Perfect Matching and Hamiltonian Circuit problems.
The sequential time complexity and the parallel (NC) processor complexity of
counting all the solutions to these two problems are shown to be
O(n^{19}log(n)) and O(n^{19}) respectively.
And thus we prove a result even more surprising than NP = P, that is, #P = FP,
where FP is the class of functions, f: {0, 1}* –> N, computable in polynomial
time on a deterministic model of computation such as a deterministic Turing
machine or a RAM. It is well established that NP subseteq P^{#P}, and hence the
Polynomial Time Hierarchy collapses to P.
———————————
Would like to hear from the experts some feedback.
Thank you,
-Javaid Aslam
9 May 2009, 1:16 pmkacamata hitam pria:
Arthur Jaffe, founder of the Clay Institute, told me at the 2009 joint math meetings that he thinks that Yang-Mills is the hardest of the Clay Millennium Problems, partly because you have to prove it for every gauge group.
25 October 2019, 4:16 am