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

tchow@xxxxxxxxxxxxx wrote: 

Here's another approach that doesn't seem to have been explored much.
Let D be the set of all polynomially clocked DTM's that reject themselves
as input.  Is D in NP?  If you can prove that it is, then you've proved
that P != NP.  If you can prove that it isn't, then you've proved that
NP != EXPTIME.  Either would be a major achievement.  And one or the
other must be true!

Regarding the Baker-Gill-Solovay result, one could also try to analyze the diagonalization construction to see exactly where the difficulties arise when trying to prove P != NP. Dexter Kozen's paper "Indexings of Subrecursive Classes" [1] does just this. If I understand it correctly, the problem is that the standard indexing using clocked DTMs, while convenient for defining the diagonalization, is provably intractable for actually calculating with. Quoting from the conference version of the paper:

"... For example, we are able to show that for the commonly used indexing of PTIME mentioned above, uniform simulation of PTIME cannot be done in PSPACE, and no simple diagonal argument over this indexing can be used to show PTIME != PSPACE."

In the paper, Kozen goes on to show that if P != NP, then it IS provable via a diagonalization argument, but presumably the indexing required would be something quite unusual (i.e., to figure out the indexing, you'd probably already have to know how to show P != NP).

[1] Dexter Kozen, "Indexings of Subrecursive Classes", Theoretical Computer Science, Vol. 11, pgs. 277-301 (1980)

--
Kurt Van Etten
kurt (at) learning (concat) computation (dot) com
http://www.learningcomputation.com/blog/
.