Re: Decidability of P versus NP
 From: Aatu Koskensilta <aatu.koskensilta@xxxxxxxxx>
 Date: Mon, 17 Apr 2006 04:56:51 +0300
Stephen MontgomerySmith 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 LogicoPhilosophicus
.
 FollowUps:
 Re: Decidability of P versus NP
 From: Stephen MontgomerySmith
 Re: Decidability of P versus NP
 References:
 Decidability of P versus NP
 From: none
 Re: Decidability of P versus NP
 From: Aatu Koskensilta
 Re: Decidability of P versus NP
 From: none
 Re: Decidability of P versus NP
 From: Aatu Koskensilta
 Re: Decidability of P versus NP
 From: Stephen MontgomerySmith
 Decidability of P versus NP
 Prev by Date: Sine or Cosine Wave Equation?
 Next by Date: Re: differential equations
 Previous by thread: Re: Decidability of P versus NP
 Next by thread: Re: Decidability of P versus NP
 Index(es):
Relevant Pages
