UConn Math Club
The P vs. NP Problem
Alex Russell (University of Connecticut)
Wednesday, October 18, 2017
The "P vs. NP" question is a celebrated open question with striking consequences for combinatorial optimization, combinatorics, and the role of human creativity in mathematics. We will begin with a definition of the computational complexity classes P and NP, and give a number of examples to indicate why the class NP is interesting. We will discuss the notion of NP-completeness and remarkable formulations of NP associated with the notion of "probabilistically checkable proofs."
Comments: Free pizza and drinks!