[FOM] "Diagonal arguments relativize"
Timothy Y. Chow
tchow at alum.mit.edu
Sun Nov 28 18:47:14 EST 2004
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
More information about the FOM
mailing list