Re: Can EXPTIME and NP be separated via diagonalization?

On Aug 4, 10:32 am, tc...@xxxxxxxxxxxxx wrote:
In article <5a915542-af50-4509-95da-fba73a7ff...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

<cplxp...@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

On Aug 4, 10:32 am, tc...@xxxxxxxxxxxxx wrote:
In article <5a915542-af50-4509-95da-fba73a7ff...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

<cplxp...@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


OK, that's very interesting. I think, based on what you've said, I
can prove an interesting fact, although my proof may be incorrect.

(Also, I took your advice and read much of Fortnow's paper on the role
of relativization in complexity theory. I think I have a bit of a
better understanding of it now.)

Anyway, I was looking through some old posts on this forum, and I
found that someone (I think it may actually have been you) posted a
very interesting decision problem: The language D of all polynomial-
time DTMs that reject themselves. It's easy to see that D must not be
a member of P, because if it were, M running on itself would have to
both accept and reject. I don't know how to prove that it runs in
exponential time (EXPTIME), but I believe that it does.

Here is where it gets interesting. Assume, for the sake of
contradiction, that there exists a deterministic Turing machine T that
decides whether or not any language X is an element of NP. If T
exists, then T can decide whether or not D is a member of NP. As was
mentioned by the original author of the post, proving that D is in NP
amounts to a proof that P != NP, and proving that D is not an element
of NP proves that NP != EXPTIME. As you have said, both of these
results cannot be proven except by nonrelativizing techniques.
Clearly, the algorithm X can still decide membership in NP in
relativized models; thus we have a contradiction, because we've found
a proof either that P != NP or that NP != EXPTIME, without having a
nonrelativizing proof.

If my argument is correct, this means that there is no algorithm that
decides membership of a language in NP.

Furthermore, I think many interesting results can be derived from that
fact, if my proof of it is valid.

-Phil
.