#### HOW HARD IS A HARD PROBLEM?

Professor Robin Wilson   Introduction As in my last lecture, I’ll be telling you today how you can earn a million dollars. Last time I offered you the chance to earn this amount by solving the Riemann hypothesis, a problem relating to prime numbers – sadly, none of you has yet come forward with a solution. This time, my problem is concerned with algorithms, which are procedures for solving problems. It’s known as the ‘P versus NP problem’, and is concerned with how hard it is to solve problems. Its solution would be of great theoretical interest to both mathematicians and computer scientists, and also of enormous practical importance in operations research and business economics. Let me remind you of where the million dollars come in. In May 2000 in Paris, the Clay Mathematics Institute, set up with the mission ‘to increase and disseminate mathematical knowledge’, hosted a meeting called A celebration of the universality of mathematical thought. The central theme of this meeting was the announcement of seven so-called ‘millennium problems’, with a prize of one million dollars for the solution to each, in order to celebrate mathematics in the new millennium. The timing of their announcement was deliberate: it celebrated the centenary of the most famous lecture ever given in mathematics – David Hilbert’s lecture at the International Congress in 1900, also in Paris, when he listed the 23 problems that he most wanted to see solved in the twentieth century. Some of these were indeed solved, while others have remained open to this day. These seven millennium problems are the problems considered by the mathematical community to be the most difficult and important in the subject – the ‘ Himalayas of mathematics’. They’re all highly technical and some are extremely difficult to describe, but very roughly they’re as follows:

• the Riemann hypothesis (relating to prime numbers);

• the P = NP? problem (on the efficiency of algorithms for solving problems);

• the Poincaré conjecture (on surfaces in four-dimensional space) – this is the only one of the seven that may be nearing a solution;

• the Navier-Stokes equation (solving a partial differential equation arising from the motion of fluids);

• Yang-Mills theory (relating to the mathematical treatment of some quantum physics);

• the Birch-Swinnerton-Dyer conjecture (another problem from number theory);

• and finally the Hodge conjecture (a highly technical problem from geometry and topology).