Relativizations of complexity classes

In a paper published in 1988, Yuri Gurevich gave a precise mathematical formulation of the central question in descriptive complexity - is there a logic capturing P - and conjectured that the answer is no. In the same paper, he also conjectured that ...

We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $${\mathsf{P}}$$P and $${\mathsf{PSPACE}}$$PSPACE, short of proving lower bounds ...

Due to the work of Baker, Gill and Solovay [SIAM J. Comput., 4 (1975), pp. 431–442] and others, it has become a paradigm that important open questions about complexity classes do not relativize. This paper develops restrictions of the standard oracle ...