Return to Colloquia & Seminar listing
Oracular Complexity Classes and Relativizing P =? NP
Student-Run Discrete Math Seminar| Speaker: | Dustin Pluta, UC Davis |
| Location: | 2112 MSB |
| Start time: | Thu, Feb 7 2008, 3:10PM |
In 1975, Baker, Gill, and Solovay proved that there exist oracles A and B such that P^A \neq NP^A and P^B = NP^B. I will give an introduction to oracle machines and oracular complexity classes and from there discuss the various results of the BGS 75 paper along with some other oracular oddities. While oracles can be a useful tool in complexity theory, they fail to help us in the P =? NP problem and give a somewhat concrete indication of how difficult this problem is (--although the problem turns out to be even harder than what BGS 75 suggests).