Re: Decidability of P = NP

In article <7b54c2b7-6ae2-43ce-b588-b564d69f3430@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@xxxxxxxxx> 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
.

Relevant Pages

  • Re: Decidability of P = NP
    ... An algorithm can only "decide" things in the sense of attaching a 0 or a 1 ... undecidable," one must implicitly or explicitly specify a formal system ... you never make reference to any formal system. ... way I can see of making sure that your algorithms *correctly* decide SAT ...
    (comp.theory)
  • Re: Whats wrong with this proof that P = NP?
    ... Given any such formal system, ... it doesn't halt. ... so there must be some flaw in your reasoning. ... applied explicitly to formal systems of reasoning about algorithms. ...
    (comp.theory)