Can EXPTIME and NP be separated via diagonalization?
- From: cplxphil@xxxxxxxxx
- Date: Sat, 2 Aug 2008 09:02:39 -0700 (PDT)
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
.
- Follow-Ups:
- Prev by Date: Java based sat solver
- Next by Date: Re: obvious ("dumb") question about oracles and P vs. NP
- Previous by thread: Java based sat solver
- Next by thread: Re: Can EXPTIME and NP be separated via diagonalization?
- Index(es):