[FOM] relativised complexity classes

Alasdair Urquhart urquhart at cs.toronto.edu
Wed Nov 11 11:05:28 EST 2015


A PSPACE-complete oracle such as TQBF (true quantified Boolean
formulas) collapses P to PSPACE.  Since NP is a subset of PSPACE,
an oracle separating P from NP also separates P from PSPACE.

On Tue, 10 Nov 2015, 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?
> Martin




More information about the FOM mailing list