What are the Millenium Prize Problems?

Originally written for the CEBE blog by Jennifer Alonso Garcia
Contributing Writer in collaboration with CEBE

Link to the original post

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", 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. 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.

For more regular content

• Follow us on Facebook: https://www.facebook.com/thevoice.loko
• Check out our Instagram page: https://www.instagram.com/thevoice.kuleuven/
• Listen to our podcasts on: https://www.mixcloud.com/The_Voice_KUL_Student_Radio

For submissions or applications

• Email us at thevoice@loko.be
• Or message us on Facebook