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

In article <1138108631.839365.257850@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<examachine@xxxxxxxxx> wrote:
>Speaking out of ignorance, I have seen many proof attempts
>working on the details of a specific NP-Complete problem such as
>SAT. Would that be a good strategy?

Certainly if P = NP then a promising way to prove it would be to exhibit
an algorithm for a specific NP-complete problem.

Also, neither Baker-Gill-Solovay nor Razborov-Rudich provide any direct
reason why you couldn't prove P != NP by studying SAT.

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!
--
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
.