UConn Math Club

The P vs. NP Problem

Alex Russell (University of Connecticut)

Wednesday, October 18, 2017 5:45 pm
MONT 314

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!