一个未解的问题

（转自2006年国际数学家大会官方网站）

Plenary Session: Avi Wigderson

An Unsolved Problem
What itinerary should a commercial traveller follow, who has to pay visits to different places on a map? Behind this apparently commonplace question lies one of the most taxing problems for mathematicians involved in computation. This is one of the NP or “non-deterministic” polynomial problems; problems whose solution can be verified quickly. On the other hand, there exist P or “deterministic” polynomial problems; problems that can be solved reasonably quickly. In 1971, Stephen Cook and Leonid Levin posed the following question: Do P and NP belong to the same class of problems? Mathematician Avi Wigderson will deal with this “confrontation” in his plenary lecture during the ICM in Madrid.

This question, first posed almost forty years ago, has yet to be answered and is the object of much attention in the world of mathematics. Indeed, it is one of the seven problems the solution to which the Clay Institute is offering an award of one million dollars each. The importance of the problem cannot be underestimated, since as Wigderson explains, “the search for the solution, and more generally, understanding the power and the limits of efficient computation, have led to the development of the Theory of Computational Complexity”. This Princeton mathematician will relate the problem, which for many years was considered a question for computer science, to mathematics. “I will try to explain why this problem, and others belonging to computational complexity, are not just mathematical problems, but problems about mathematics itself, and ones which mathematicians are obliged to tackle”, says Wigderson in the introduction to his lecture.

It is quite likely that the commercial traveller referred to at the beginning will not care which class the problem belongs to, either P or NP. “That’s a question for mathematicians”, he will say. But he should know that if it proved to belong to the same class, it would be a problem whose solution is be easy to find, and could really provide the answer to his own problem: how to make all the visits on his schedule in less time and cut down on fuel consumption. In that case he might find the P and NP question a little more relevant.

Avi Wigderson was born in 1956. He graduated in Computer Science at Technion, the Technological Institute of Israel. Three years later, he obtained his doctorate at Princeton (USA). Since 1999 he has taught at the Institute of Advanced Studies at Princeton. Prior to that he taught at the Hebrew University in Jerusalem, with sojourns as visiting professor at various universities in the United States. Recognition of his work in the field of computation figures in his curriculum, the most outstanding being the Nevalinna Prize, awarded to him at the International Congress of Mathematicians in Zurich in 1994.

Speaker: Avi Wigderson

Title: P, NP and Mathematics: A Computational Complexity Perspective

Date: Wednesday, August 23rd: 10:15-11:15

ICM2006 Scientific Programme: http://www.icm2006.org/scientificprogram/plenarylectures/

P v NP: http://www.claymath.org/millennium/P_vs_NP/