Graduate Pizza Seminar
P vs. NP: the million-dollar question
Matthew Hohertz -- Rutgers University
Date & time: Friday, 06 April 2018 at 1:40PM - 2:40PM
|Still open eighteen years after the Clay Institute offered $1 million for its solution, the P vs. NP problem poses a simply-stated question: Can we quickly solve a mathematical problem if we can quickly verify a proposed solution to the same problem? We begin this seminar by introducing the basic structures of complexity theory, including Turing machines and decision problems. After phrasing the P vs. NP problem rigorously, we examine some common proof techniques of complexity theory and prove the undecidability of P vs. NP under their underlying assumptions alone. Finally, we discuss NP-complete problems — the "hardest" of all NP problems — and the intimate (and perhaps surprising) ties between their solutions and the answer to the broader P vs. NP problem.