## 14 Jan Million-dollar math problems

In 2000, the Clay Mathematics Institute noted seven fundamental math problems that were still unsolved at that time (the Millenium Problems). If a proof for one of these problems could be given, the researcher would be awarded a million (US) dollars.

Easy money right?! A bit of work and seven million dollars will be deposited into your bank account. But don’t underestimate the difficulty of these problems: as of today only one of them, the Poincaré Conjecture, has been solved. And the person who solved it didn’t even want his prize money.

## The Poincaré Conjecture

The Poincaré Conjecture is a theorem from topology, where properties of objects are studied. Properties that are preserved under taking homeomorphisms: functions that transform the object without tearing it. **Think of taking homeomorphisms as transforming a piece of clay in your hand.** **You can make a sphere of the clay and, with a little finger work, you can transform it into a cube, or a banana. But there’s a rule: you cannot add or remove holes.** So if you start with a donut, you cannot transform it into a sphere, or into the number eight. You can, however, transform it into a cup with an ear. We say that the donut is homeomorphic to the cup.

The conjecture states that every simply connected, closed 3-manifold is homeomorphic to the 3-sphere. This means that every 3-dimensional object that has no holes (simply connected) and is finite (closed) – so not infinitely large – is homeomorphic to a sphere (every object you can imagine without holes can be reshaped into the sphere).

This may seem obvious, but the proof was nonetheless very hard to find. It was given by Grigori Perelman, a Russian mathematician. In 2010 he turned down the prize of one million dollars. He said it was unfair and that Richard Hamilton, another mathematician, had an equal contribution to the proof. How noble of him!

## The Navier-Stokes equation

Most of the remaining six problems have applications in other sciences, like the problem of the Navier-Stokes equation. **This describes the motion of fluids in two and three dimensional spaces and can be used to model ocean currents, the weather and air flow around the wing of an airplane.**

We want solutions of this equation to be smooth and physically reasonable (see this article for more information). However, there is no proof that such solutions exist. But why not? We use this equation a lot, haven’t we found several solutions already?

Well, we currently find solutions by approximating them using a computer. So we do know of solutions that agree with the equation, we just aren’t a 100% sure. What’s more, we need proof that the solutions have a bounded energy (this is what is meant by physically reasonable). We cannot have solutions that blow up to infinity!

A proof can have many applications. It would help a lot towards our understanding of turbulence, and therefore it can lead to better airplane design. But it might give insight into a lot more. Even weather prediction could be improved!

## The P vs NP problem

My personal favourite is the P vs NP problem. This is also a fundamental problem in theoretical computer science and it says something about the speed of algorithms for solving certain problems. We call this complexity. An algorithm is what a computer uses to solve a problem. It is a set of steps the computer has to follow in order to find a solution. We can say something about the time it takes for a computer to do this. We do not express this time in seconds, because that depends on the hardware you are using. We measure it in the amount of operations the computer uses. For example, some sorting algorithms are solved in *n^2* time. So if we have a list of *n *integers, the algorithm to sort this list does this with approximately *n^2* operations (video).

If we have a problem of size *n* that can be solved in *T(n) =* *n^2* time, we say that *T(n)* grows at the order of *n^2*. And thus it can be solved in polynomial time, and we say that this problem is in P (the P stands for polynomial). P is just a class of problems that can all be solved in polynomial time.

NP stands for nondeterministic polynomial time, and it describes a class of problems for which the solution can be *verified* in polynomial time, but the solution cannot be *found* in polynomial time.

Suppose that you are having a party and you can invite 100 people. But, some relatives and friends are in a fight, and can therefore not both be invited. You now have to find a list of 100 people and none of these can be on bad terms with each other. If you have such a list, it is fairly easy to check if all the invited are ok with each other. But making up such a list from scratch takes a lot of time. A computer couldn’t do it in polynomial time. Therefore, this problem is in NP.

The question is whether or not these classes of problems are the same. If it is possible to check the correctness of a solution to a problem quickly, can the solution itself also be found quickly? If P = NP there would be great consequences. There wouldn’t be a difference between finding a solution or checking one. Cryptography, which relies on the difficulty of finding such solutions, would fall apart and we would need to get rid of every protocol that is used nowadays to encrypt data. **Think about it this way: if someone can appreciate a beautiful painting, would that person also be able to make it themselves?** Most mathematicians and computer scientists believe that P is not equal to NP. But a formal proof has yet to be given.

## Do something!

To find out about the other problems: visit the Clay Mathematics Institute or google “millennium problems”. If you could give a proof for one of these problems, you will certainly be included in several history textbooks. You could be the person that enables meteorologists to finally make reliable weather predictions that go beyond three days. Or we could design airplanes that never suffer from turbulence again. A lot of scientists are still working on these problems, and will be for the foreseeable future. So if you feel motivated, start a career in mathematics!

WTFmarlou

## No Comments