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
.