What are the Millennium Prize problems?

Jennifer Alonso García · 14-01-2021 10:00 · CEBE answers

It will not come to you as a surprise if I tell you that mathematicians love problems. Our lives revolve around finding and trying to solve problems. Often, we observe natural phenomena and wonder whether mathematics could help us to formally model their dynamics to further advance our understanding of the world. Sometimes, we discover problems and study theories that might not have a direct practical application. Luckily, more often than not, these theories, formerly viewed as “useless” have led to breakthroughs in science and technology. For example, number theory was seen as “useless” until Ron Rivest, Adi Shamir and Leonard Adleman created the RSA algorithm that since 1977 allows for secure data transmission.

Some of these mathematical challenges are what the Clay Mathematics Institute, based in New Hampshire (United States), calls the "Millennium Prize Problems". This institute selected seven important classic questions that had resisted solution by 2000. These problems were the “Poincaré conjecture”; the “P vs NP”; the “Hodge conjecture”; the “Riemann hypothesis”; the “Yang-Mills and mass gap”; the “Navier-Stokes equation”, and the “Birch and Swinnerton-Dyer conjecture”. To date, only the “Poincaré conjecture” has been solved, in this case by Russian mathematician Grigori Perelman in 2003. His result proves that 3-dimensional spaces without holes (a donut is an example of a space with a hole) can be deformed to a 3-dimensional sphere.

Among the unsolved remainder, let us focus on the fascinating "P vs NP problem".  

This is considered by many experts the most important open problem in computer science. Why? Think of a Sudoku grid which is an example of a NP problem. But first, let´s explain what a P problem is: If I give you a potential solution of a Sudoku grid, then it is easy to verify the solution. The time to check the solution increases with the grid, but it does not explode. In the case of the NP problem we find the inverse problem: Finding a solution to a Sudoku grid is hard and the bigger the grid the slower it becomes to find a solution. NP problems are difficult to solve but easy to check once we have found the solution (see graph). On the other hand, I can find solutions quickly for P problems.

Most computer scientists think that P is not equal to NP, as nobody has been able to prove yet that P = NP in well-known NP problems. The solution to this “Millenium Prize” problem would have great implications in our daily life. For example, if P=NP is true then it would mean that cryptography, an NP problem which is the mathematical base of all our online security systems, should be fully rethought. Think of accessing your email account. It is super easy to access if you know the password, but it is extremely hard to find the password if you do not know it already. If P=NP then it will be possible to create an algorithm that finds the password easily. Not all is bad news if P = NP because we would be able to solve many important problems in, for instance, logistics. Think of a salesman problem. For a given list of cities and distances, what is the shortest possible route that goes from the origin city to each city exactly once and returns to the origin city? It sounds easy, but it is actually a very hard optimization problem. If it is proven that P is not equal to NP, it would have less practical computational benefits but would clarify once for all that it is just not possible to develop quick algorithms to solve all problems. That would shift the focus of researchers to finding partial solutions instead of exact ones. Either way, very cool right?

In case you find some free time and solve one of these problems (you can find more info about the other ones here), you will help advance humanity and feed your savings account with a US$1 million prize.

Comments

Leave a comment


Collaborative partners

This blog is supported by the Arts and Culture section of the Spanish Embassy in Belgium and by the Brussels section of the “Instituto Cervantes”, under the SciComm initiative #SPreadScience.

Instituto Cervantes Arts and Culture section of the Spanish Embassy

Disclaimer: The content of each post in “A Spoonful Of Science” is the responsibility of the corresponding author(s). Therefore, the viewpoints expressed on the blog are those of the author(s) of each post, which do not necessarily reflect the viewpoints, thoughts and opinions of CEBE members and representatives.

Would you like to send us a question?

“Do you have a burning question that you would like a scientist to answer? Or a topic you would like to learn about? Send it to us!”

Categories

CEBE answers (13 Blogs)
Science Chronicles (13 Blogs)
Gender equality in science (7 Blogs)
Winners "Your research in one image or 1000 words" - 1st Edition (7 Blogs)
Webinars (5 Blogs)
CEBE's online events (1 Blogs)