Relativizations of complexity classes

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

A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from exponential space by showing that all Turing complete sets ...

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