William Mong Distinguished Lecture by Professor Avi Wigderson

The "P vs. NP" problem: efficient computation, Internet security, and the limits to human knowledge

Avi Wigderson is a Professor at the School of Mathematics, Institute for Advanced Study, Princeton. His main research interests include randomness and computation, algorithms and optimization, complexity theory, circuit complexity, proof complexity, quantum computation and communication, cryptography and distributed computation. He also organizes the school activities in Computer Science and Discrete Mathematics (CSDM).

The "P vs. NP" problem, formulated by computer theorists in the 1970s, quickly became a central outstanding problem of science and mathematics. In this talk, the speaker will attempt to describe its mathematical, scientific and philosophical content. He will also discuss its status, and the implications of its resolution on science and technology.