[FOM] relativised complexity classes

[Timothy Y. Chow]

Martin Davis wrote:

> The well known Gill,Baker,Solovay theorem states that relative to a 
> computable oracle, the classes P and NP can be either equal or unequal, 
> depending on the specific oracle. What is known concerning similar 
> results for other complexity classes? In particular what about P and 
> PSPACE?

P and PSPACE admit contradictory relativizations as well.  To make them 
equal, take a PSPACE-complete oracle.  To make them unequal, use the same 
Baker-Gill-Solovay oracle that separates P from NP.

In general, for almost any open problem in complexity theory of the form 
"Does class X equal class Y?" there are known contradictory 
relativizations.

Conversely, if there are known contradictory relativizations, then usually 
the problem is still open.  The main exceptions involve complexity classes 
related to interactive proofs.  But Aaronson and Wigderson have a 
generalization of the relativization technique that they call 
"algebrization" that in some sense encapsulates the "trick" used in 
interactive proofs, and shows that the same trick can't be used for most 
other complexity class separations.

Tim