home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / logic / 2052 < prev    next >
Encoding:
Internet Message Format  |  1992-11-15  |  2.3 KB
  1. Xref: sparky sci.logic:2052 sci.math:15021
  2. Path: sparky!uunet!pipex!warwick!uknet!pavo.csi.cam.ac.uk!camcus!gjm11
  3. From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
  4. Newsgroups: sci.logic,sci.math
  5. Subject: Re: Logic and Mathematicians
  6. Message-ID: <1992Nov16.050846.15982@infodev.cam.ac.uk>
  7. Date: 16 Nov 92 05:08:46 GMT
  8. References: <1992Nov12.204959.17389@husc3.harvard.edu> <1992Nov14.141234.26280@email.tuwien.ac.at> <1992Nov15.220359.21971@guinness.idbsu.edu> <1992Nov15.191744.17481@husc3.harvard.edu>
  9. Sender: news@infodev.cam.ac.uk (USENET news)
  10. Organization: U of Cambridge, England
  11. Lines: 39
  12. Nntp-Posting-Host: apus.cus.cam.ac.uk
  13.  
  14. In article <1992Nov15.191744.17481@husc3.harvard.edu>, zeleny@husc10.harvard.edu (Michael Zeleny) writes:
  15.  
  16. > RZ:
  17. > >>Oh yes: Prove P=NP is independent of ZFC. It actuall HAS
  18. > >>been shown independent in some weak arithmetics.
  19. > 
  20. > Funny, I would have thought independence to be indicative of
  21. > foundational profundity, rather than triviality.
  22. > 
  23. > >>-- 
  24. > >>Richard Zach                         Technische Universitaet Wien
  25. > >>[zach@csdec1.tuwien.ac.at]     Abteilung fuer Formale Logik 185.2
  26. > 
  27. > RH:
  28. > >Wouldn't that actually answer the question?
  29. > 
  30. > Only from the standpoint of a formalist.
  31.  
  32. The following isn't very profound, but I had to think it out to work out
  33. who was right on this one. I'm posting it mostly to save other people the
  34. trouble of doing it themselves. :-)
  35.  
  36. If P=NP is independent of ZFC, then ZFC does not prove P=NP, so you can't
  37. write down an algorithm for (say) the travelling salesman problem and prove
  38. it's in P using only ZFC. I suppose there might be an algorithm that you
  39. could write down but that you couldn't prove (in ZFC) to be in P. (A bit
  40. like with Goodstein's theorem, where there's an "algorithm" you can write
  41. down but you can't prove it terminates unless you use something stronger
  42. than PA.)
  43.  
  44. So no, it wouldn't actually answer the question. If any "plausible"
  45. extension of ZFC proved P=NP, then there would be an algorithm for (e.g.)
  46. travelling salesman that was "plausibly" in P. What if it were done with,
  47. say, a forcing argument? Suppose P=NP holds in some generic extension of V.
  48. Then ... I don't know; I can't think about forcing at 5am. Oh well.
  49.  
  50. -- 
  51. Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
  52. gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
  53.