🚀 go-pugleaf

In article <1992Nov16.050846.15982@infodev.cam.ac.uk> gjm11@cus.cam.ac.uk (G.J. McCaughan) writes:
>In article <1992Nov15.191744.17481@husc3.harvard.edu>, zeleny@husc10.harvard.edu (Michael Zeleny) writes:
>
>> RZ:
>> >>Oh yes: Prove P=NP is independent of ZFC. It actuall HAS
>> >>been shown independent in some weak arithmetics.
>> 
>> Funny, I would have thought independence to be indicative of
>> foundational profundity, rather than triviality.
>> 
>> >>-- 
>> >>Richard Zach                         Technische Universitaet Wien
>> >>[zach@csdec1.tuwien.ac.at]     Abteilung fuer Formale Logik 185.2
>> 
>> RH:
>> >Wouldn't that actually answer the question?
>> 
>> Only from the standpoint of a formalist.
>
>The following isn't very profound, but I had to think it out to work out
>who was right on this one. I'm posting it mostly to save other people the
>trouble of doing it themselves. :-)
>
>If P=NP is independent of ZFC, then ZFC does not prove P=NP, so you can't
>write down an algorithm for (say) the travelling salesman problem and prove
>it's in P using only ZFC. I suppose there might be an algorithm that you
>could write down but that you couldn't prove (in ZFC) to be in P. (A bit
>like with Goodstein's theorem, where there's an "algorithm" you can write
>down but you can't prove it terminates unless you use something stronger
>than PA.)

This is exactly what I was thinking about.  There would also have to
be some algorithm that one could not prove to not be in P.  Would this
algorithm have to be "objectively" in P?

>
>So no, it wouldn't actually answer the question. If any "plausible"
>extension of ZFC proved P=NP, then there would be an algorithm for (e.g.)
>travelling salesman that was "plausibly" in P. What if it were done with,
>say, a forcing argument? Suppose P=NP holds in some generic extension of V.
>Then ... I don't know; I can't think about forcing at 5am. Oh well.
>
>-- 
>Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
>gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]


-- 
The opinions expressed		|     --Sincerely,
above are not the "official"	|     M. Randall Holmes
opinions of any person		|     Math. Dept., Boise State Univ.
or institution.			|     holmes@opal.idbsu.edu