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