[FOM] "Diagonal arguments relativize"

[Timothy Y. Chow]

I was musing again about the topic of my first post to FOM, and in 
particular about Alasdair Urquhart's followup question, "What do
people mean by, `Diagonal arguments relativize'?"  I had a small
insight into the matter, which I'm sure many others have had too,
but I don't recall seeing it stated exactly this way before, so I
thought I'd mention it.

Let's recall the standard argument that P != EXP.  One defines

   D = {all polynomially clocked machines that reject themselves as input}

Then one shows that

1. D is not in P, and
2. D is in EXP.

To say that this argument relativizes is just to say that it remains valid 
when an oracle is added througout.

The small insight I had is that even though "P = NP" and "NP = EXP" have 
contradictory relativizations, this does *not* imply that it is hopeless
to try to prove either

3. D is in NP, or
4. D is not in NP.

Indeed, either 3 or 4 must be true.  All we know is that to prove either
3 or 4, we have to use a *nonrelativizing argument*.

In other words, one should not be misled by the statement that "diagonal 
arguments relativize" into thinking that there is no point in trying to
consider the set D when trying to separate P and NP (or NP and EXP).

By the way, is there a general consensus as to which of 3 or 4 is likely
to be true?  I would think 4 is true, since it seems unlikely to me that
one can decide D significantly faster than by the obvious method (i.e.,
by direct simulation) even if a polynomial-sized certificate is provided.

Tim