[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