Can EXPTIME and NP be separated via diagonalization?




Hi,

I was wondering if it might be possible to separate EXPTIME and NP via
diagonalization. I ask because I cannot think of an oracle A such
that EXPTIME^A = NP^A. (I don't think an EXPTIME-complete problem
would work, would it?) Has there been a result akin to the Baker-Gill-
Solovay result for EXPTIME and NP (as opposed to for NP and P)?

The reason I ask is because I think I have an approach to proving that
NP != EXPTIME, although I haven't thought it through sufficiently to
be sure if it would work.

-Phil
.