Re: Can EXPTIME and NP be separated via diagonalization?

In article <5a915542-af50-4509-95da-fba73a7ff6ed@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@xxxxxxxxx> wrote:
Has there been a result akin to the Baker-Gill-
Solovay result for EXPTIME and NP (as opposed to for NP and P)?

Yes, there is. I don't remember offhand who proved it first. In general,
most unsolved separations have contradictory relativizations, except for
those involving space-bounded complexity classes (for which there are
subtle problems with defining oracles correctly), or those involving some
relatively arcane complexity classes. Fortnow's paper "The role of
relativization in complexity theory" is a good place to start familiarizing
yourself with this area.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Quantcast