The P vs. NP Problem
April 25, 2016
Bailey Hall 207
Refreshments will be served in Bailey Hall 204 4:45pm
I'll discuss the status of the famous P = NP problem in 2016, offering a personal perspective on what it's about, why it's important, why many experts conjecture that P ≠ NP is both true and provable, why proving P≠ NP is so hard, the landscape of related problems, and crucially, what progress has been made in the last half-century. I'll say something about diagonalization and circuit lower bounds; the relativization, algebrization, and natural proofs barriers; and the recent works of Ryan Williams and Ketan Mulmuley, which (in different ways) hint at a duality between impossibility proofs and algorithms.
|Union College Math Department Home Page|
Comments to: firstname.lastname@example.org
Created automatically on: Sun Jul 15 19:00:11 EDT 2018