Return to Colloquia & Seminar listing
Combinatorics in Classical Computation Theory
Student-Run Discrete Math Seminar| Speaker: | Rob Gysel, UC Davis |
| Location: | 2112 MSB |
| Start time: | Thu, Nov 29 2007, 3:10PM |
Combinatorial problems are ubiquitous in the classical theory of computation. We begin with an accessible description of computational complexity, defining what is needed to intuitively grasp the distinction between the complexity classes P, NP, and NP-Complete. The unresolved relationship between P and NP serves as motivation for considering the boolean satisfiability problem (SAT), whose relationship with NP is illuminated by Cook's Theorem. In 1972, Karp described 21 combinatorial and graph theoretic problems and their importance to NP via their relationship to SAT.