The P vs. NP Problem

The P vs. NP problem was formulated about 50 years ago, and was chosen to be one of the seven Clay millenium problems 25 years ago. In this period our understanding of the depth, breadth and impact of the problem has changed dramatically. I plan to explain the problem, and some of the many research directions and scientific connections it has led to.