🚀 go-pugleaf

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.)

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]