Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Food For Thought Seminar

Christian Woods

UCSD

Millennium Problem Series: \textbf{P} vs. \textbf{NP}

Abstract:

This is the first in a series of seven Food for Thought talks on the Millennium Prize Problems. In this talk we give an introduction to the Clay Mathematics Institute and its Millennium Prize Problems program. We then focus our attention on the question of whether \textbf{P}, the class of problems with polynomial-time algorithms, equals \textbf{NP}, the class of problems with polynomial-time nondeterministic algorithms. We will define \textbf{P} and \textbf{NP} in terms of Turing machines. We will then move on to some diverse contemporary approaches to proving either \textbf{P} = \textbf{NP} or \textbf{P} $\neq$ \textbf{NP}, and discuss the implications that such a theorem would have. Along the way, we will see some famous results that have appeared out of the struggle to solve this hallmark riddle of theoretical computer science.

November 21, 2013

12:00 PM

AP&M 5402

****************************