Decidability of P = NP

Here's an approach I thought of for to trying to show that the P vs NP
question might be undecidable. Any comments would be appreciated.

According to Baker-Gill-Solovay, there exist oracles A and B such that
P^A = NP^A and P^B != NP^B. As a result, it is concluded that P = NP
cannot be proven true or false by techniques that relativize.

Now consider a Turing machine that partially decides the language Q of
languages that are in P. By Rice's theorem, the language Q is
necessarily undecidable. However, that doesn't mean that it is
impossible for a TM to partially decide the language.

Now consider the language SAT. Assume, for the sake of contradiction,
that the TM that partially decides Q (call it R) is able to decide
whether or not SAT is in Q. If it can, then R^B, where B is the
oracle set s.t. P^B != NP^B, is also capable of deciding whether SAT
is in Q. The same holds for R^A, where A is defined as above also.

If this is true, however, then we have a proof technique that
relativizes. Running the same algorithm relative to different oracle
sets is a simple relativization of the proof technique; thus we have
found a proof that P = NP or that P != NP using a technique that
relativizes.

This contradiction shows that no TM can decide whether or not SAT is
in P, and thus no TM can decide if P = NP. Thus, either P = NP is
undecidable, or the computational model associated with the oracle
sets mentioned are inconsistent--which doesn't seem likely.

Any comments on this approach?

Thanks,
Phil

In article <7b54c2b7-6ae2-43ce-b588-b564d69f3430@k7g2000hsd.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>Now consider the language SAT. Assume, for the sake of contradiction,
>that the TM that partially decides Q (call it R) is able to decide
>whether or not SAT is in Q.

I think the fundamental problem with your approach is that you're confusing
two different notions of the word "decide."

An algorithm can only "decide" things in the sense of attaching a 0 or a 1
to an input that you give it. But you're trying to get your algorithms to
"decide" whether SAT is in NP in the sense of determining *correctly*
whether SAT *really* is in NP. This is an entirely different sense of
the word "decide."

Perhaps it will help to point out that when one says "P = NP may be
undecidable," one must implicitly or explicitly specify a formal system
in which P = NP is (supposedly) undecidable. For example, one might
really mean "P = NP is undecidable in first-order Peano arithmetic, PA."
But even if this is true, P = NP might still be decidable in ZFC set
theory.

In your argument, you never make reference to any formal system. The only
way I can see of making sure that your algorithms *correctly* decide SAT
is to link them to some formal system whose theorems are guaranteed to be
true. But you have not exhibited any such link, so what you're saying
doesn't really make sense.
--
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

On Aug 15, 11:12 pm, tc...@lsa.umich.edu wrote:
> In article <7b54c2b7-6ae2-43ce-b588-b564d69f3...@k7g2000hsd.googlegroups.com>,
>
> <cplxp...@gmail.com> wrote:
> >Now consider the language SAT. Assume, for the sake of contradiction,
> >that the TM that partially decides Q (call it R) is able to decide
> >whether or not SAT is in Q.
>
> I think the fundamental problem with your approach is that you're confusing
> two different notions of the word "decide."
>
> An algorithm can only "decide" things in the sense of attaching a 0 or a 1
> to an input that you give it. But you're trying to get your algorithms to
> "decide" whether SAT is in NP in the sense of determining *correctly*
> whether SAT *really* is in NP. This is an entirely different sense of
> the word "decide."
>
> Perhaps it will help to point out that when one says "P = NP may be
> undecidable," one must implicitly or explicitly specify a formal system
> in which P = NP is (supposedly) undecidable. For example, one might
> really mean "P = NP is undecidable in first-order Peano arithmetic, PA."
> But even if this is true, P = NP might still be decidable in ZFC set
> theory.
>
> In your argument, you never make reference to any formal system. The only
> way I can see of making sure that your algorithms *correctly* decide SAT
> is to link them to some formal system whose theorems are guaranteed to be
> true. But you have not exhibited any such link, so what you're saying
> doesn't really make sense.
> --
> 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

Ok, fair enough. Thanks for the feedback.

-Phil