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 Abstract: 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.