Scott Aaronson est professeur à Univesity of Texas à Austin. Il est mondialement reconnu pour ses travaux autour de l’informatique quantique et de ses limites pour la résolution de grands problèmes de complexité en informatique théorique. Scott donnera un séminaire à l’ENS Lyon (Amphi B) ce 15 décembre à 13h30.

Title: The P vs. NP Problem

Abstract: I’ll discuss the status of the 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.