
The P vs. NP Problem
Avi Wigderson of the Institute for Advanced Study gives this Members' Colloquium talk on the P versus NP problem, formulated roughly fifty years ago and named one of the seven Clay Millennium Prize problems twenty five years ago. He lays out what the problem actually asks, the gap between finding solutions and verifying them, and traces how understanding of its depth and breadth has shifted over five decades. Wigderson surveys the research directions it spawned, connecting computational complexity to cryptography, algorithm design, and other branches of mathematics and computer science, showing why a question that sounds narrow has become a hub connecting fields that otherwise look unrelated. Delivered at Simonyi Hall with remote access offered, the talk is aimed at a general scientific audience rather than specialists, building the problem up from first principles before following it outward into its many open threads.