Series: Penn State Logic Seminar

Date: Tuesday, February 5, 2002

Time: 2:30 - 3:45 PM

Place: 113 McAllister Building

Speaker: Carl Mummert, Penn State, Mathematics

Title: Relativizations of the P = NP Question


P and NP are the classes of polynomial-time computable and
nondeterministic polynomial-time computable sets respectively.  The
question of whether these two classes coincide is a famous open
problem in complexity theory.  In 1975, Baker, Gill and Solovay showed
that this question is not solvable by standard techniques of recursion
theory. In this talk, I will prove their result: There are two
oracles, A and B, such that relative to A, P equals NP, while relative
to B, P does not equal NP.  The basic concepts of oracle Turing
machines and the P = NP question will be covered, assuming basic
knowledge of ordinary Turing machines.