Up: Student Seminars for 2016
Top: Math Department Student Seminars

The P vs. NP Problem

by

Scott Aaronson
HRUMC

April 25, 2016
5:00 pm
Bailey Hall 207

Refreshments will be served in Bailey Hall 204 4:45pm


Abstract:

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.


For additional information, send e-mail to math@union.edu or call (518) 388-6246.
Up: Student Seminars for 2016
Top: Math Department Student Seminars

[HOME]
Union College Math Department Home Page
Comments to: math@union.edu
Created automatically on: Mon Jan 22 03:33:41 EST 2018