## 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!