Re: Significance of "Relativizations of the P =? NP Question"

In article <1138634606.463645.59900@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<examachine@xxxxxxxxx> wrote:
>tchow@xxxxxxxxxxxxx wrote:
>> Let D be the set of all polynomially clocked DTM's that reject themselves
>> as input.
>
>That reject their DTM encodings and accept everything else?

No, the only condition is that they reject their DTM encodings.

>And D is the language here? The decision problem is to recognize D?

Yes.

>Or if I am misunderstanding you, could you please clarify the problem a
>bit for me?

It's a classic diagonalization construction. There's an easy way
to decide D: simply simulate the DTM in question, feeding it its own
encoding, and see if it rejects itself. This can certainly be done in
exponential time---in fact, much less than exponential time.

But it can't be done in polynomial time. If it could be, then there
would be some polynomially clocked machine M deciding it. Does M reject
itself? If so, then M is in D, and hence M accepts M, a contradiction.
Similarly, if M doesn't reject itself, then M is not in D, and so M will
reject M, again a contradiction.
--
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
.

Relevant Pages