@article{ben-gil:b:random-oracle, Author = "C. ~Bennet and J. ~Gill", Title = "Relative to a random oracle {P} $\ne$ {N}{P} $\ne$ co{N}{P} with probability 1", Journal = "SIAM J. Comp.", Year = "1981", Volume = "10", Pages = "96-103" } @article{bak-gil-sol:b:rel, Author = "T. ~Baker and J. ~Gill and R. ~Solovay", Title = "Relativizations of the $\p \stackrel{\mbox{\protect\scriptsize ?}}{=} \np$ question", Journal = "SIAM J. Comp.", Year = "1975", Volume = "4", Pages = "431-442" } @article{Kur:b:random-oracle-hypothesis, Author = "S. A. ~Kurtz", Title = "On the random oracle hypothesis", Journal = "Information and Control", Year = "1983", Volume = "57", Pages = "40-47" } @incollection{sip:b:complete-oracles, author = "M. ~Sipser", title={On relativization and the existence of complete sets}, booktitle={Proc. 9th Int. Colloqu. on Automata, Languages, and Programming}, publisher="Springer Verlag", year={1982}, volume = "140", series = "Lecture Notes on Computer Science", pages={523-531}, } @book{sipser:b:intro, Author = "M.~Sipser", Title = "Introduction to the Theory of Computation", address="Boston", Publisher = "PWS Publishing Company", Year = "1997" } @book{papa:b:comp-compl, Author = "C. Papadimitriou", Title = "Computational Comopleixty", address="New York", Publisher = "Addison Wesley Publishing Compnay", Year = "1993" }