Re: Decidability of P versus NP



Stephen Montgomery-Smith wrote:
Aatu Koskensilta wrote:

none wrote:

Generally, with respect to the problem described in http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf.




There is no mathematical meaning to saying that a given statement is undecidable in an absolute sense.

But I do think that there are some statements that you can definitely say are decidable.

Sure, "5^5^5^5^5^5^5^...^5 + 7^7^7^7^7^7^7^7^...^7 + 1 is a prime" is decidable in principle by simple calculation; and Fermat's last theorem is decidable since, well, it has been decided.

For example, the Goldbach conjecture. If you can prove it is undecidable, then you have proved that there are no counterexamples, because any counterexample would constitute a disproof.

Even if Goldbach's conjecture is undecidable (say in ZFC or PA) there is no guarantee that this undecidability is provable from any principles we come to accept. This is just another way of saying that even if GC is true we might never prove it.

I cannot see how this kind of argument could apply to N=NP.

Well, I don't think there's much to the argument to begin with but you're right in that it doesn't in any immediate way apply to P=/=NP which isn't Pi_1 (although it could of course turn out to be equivalent to a Pi_1 sentence).

--
Aatu Koskensilta (aatu.koskensilta@xxxxxxxxx)

"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
.



Relevant Pages

  • Re: Alan Turings Halting Problem is incorrectly formed (PART-TWO)
    ... >> Its that only two people understood what I was saying. ... > INCORRECT QUESTION kind of undecidable. ... That has many interpretations and one of them agrees with my ... interpretation of undecidability. ...
    (sci.logic)
  • Re: Standard Model of N means standard well-ordering ?
    ... there are no pink roses because you just said ... We can prove SOME undecidability ... >write out and present the counter-models, ... mathematics Principle, beside the Induction? ...
    (sci.logic)
  • Re: Decidability of P versus NP
    ... undecidable, then you have proved that there are no counterexamples, because any counterexample would constitute a disproof. ... Even if Goldbach's conjecture is undecidable there is no guarantee that this undecidability is provable from any principles we come to accept. ...
    (sci.math)