home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / logic / 2070 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  3.3 KB
  1. Xref: sparky sci.logic:2070 sci.math:15109
  2. Newsgroups: sci.logic,sci.math
  3. Path: sparky!uunet!zaphod.mps.ohio-state.edu!rpi!newsserver.pixel.kodak.com!psinntp!psinntp!dorsai.com!mutation
  4. From: mutation@dorsai.com (Florian Lengyel)
  5. Subject: Re: Logic and Mathematicians
  6. Message-ID: <1992Nov16.222220.7956@dorsai.com>
  7. Organization: The Dorsai Embassy +1.718.729.5018
  8. X-Newsreader: Tin 1.1 PL4
  9. References: <1992Nov15.191744.17481@husc3.harvard.edu>
  10. Date: Mon, 16 Nov 1992 22:22:20 GMT
  11. Lines: 76
  12.  
  13. zeleny@husc10.harvard.edu (Michael Zeleny) writes:
  14. : In article <1992Nov15.220359.21971@guinness.idbsu.edu>
  15. : holmes@garnet.idbsu.edu (Randall Holmes) writes:
  16. : 
  17. : >In article <1992Nov14.141234.26280@email.tuwien.ac.at>
  18. : >zach@csdec1.tuwien.ac.at writes:
  19. : 
  20. : >>In article <1992Nov12.204959.17389@husc3.harvard.edu>,
  21. : >>zeleny@husc10.harvard.edu (Michael Zeleny) writes:
  22. : 
  23. : MZ:
  24. : >>>I offer Post's problem as a counterexample.  Also, it doesn't seem
  25. : >>>that there could be a solution for "P =? NP" that would render the
  26. : >>>problem silly in retrospect.
  27. : 
  28. : RZ:
  29. : >>Oh yes: Prove P=NP is independent of ZFC. It actuall HAS
  30. : >>been shown independent in some weak arithmetics.
  31. : 
  32. : Funny, I would have thought independence to be indicative of
  33. : foundational profundity, rather than triviality.
  34. : 
  35. : >>-- 
  36. : >>Richard Zach                         Technische Universitaet Wien
  37. : >>[zach@csdec1.tuwien.ac.at]     Abteilung fuer Formale Logik 185.2
  38. : 
  39. : RH:
  40. : >Wouldn't that actually answer the question?
  41. : 
  42. : Only from the standpoint of a formalist.
  43.  
  44. Would the construction of two models of ZFC,
  45.   the first, in which P = NP holds
  46.   the second, in which P <> NP holds
  47. call for two models of computation that would violate the polynomial-time
  48. Church's thesis, if not Church's thesis itself?
  49.  
  50. In the first model, the notion of computation would have an interpretation
  51. which would not be polynomially equivalent to the notion of computation in the
  52. second model. If you believe Church's thesis, the independence proof would
  53. establish that these two notions of computability encompass exactly the
  54. same class of functions. So the encoding of a polynomial time NP-complete 
  55. algorithm in the first model as an algorithm in the second model would not 
  56. be polynomial time.
  57.  
  58. If you believe the polynomial-time version of Church's thesis, this situation
  59. cannot occur (assuming that polynomial-time means the same thing in both
  60. models). 
  61.  
  62. A formalist might say: "P = NP is independent of the axioms of set theory,
  63. I cannot derive P = NP or P <> NP from ZFC, therefore the question is
  64. 'settled'", but only if the formalist would willfully overlook the
  65. construction of the computable functions and their complexity classes
  66. according to the first and second models, at least one of which would
  67. (it appears to me) involve a non-standard notion of computation.
  68.  
  69. But I must admit that these possibilities strike me as counterintuitive,
  70. because of my sense that such an independence proof would violate the
  71. polynomial time form of Church's thesis.
  72.  
  73. : 
  74. : >-- 
  75. : >The opinions expressed             --Sincerely,
  76. : >above are not the "official"         M. Randall Holmes
  77. : >opinions of any person             Math. Dept., Boise State Univ.
  78. : >or institution.                 holmes@opal.idbsu.edu
  79. : 
  80. : cordially,
  81. : mikhail zeleny@husc.harvard.edu
  82. : " -- I shall speak bluntly, because life is short."
  83.  
  84. Ordinally,
  85.  
  86. -- 
  87. MUTATION@DORSAI.COM
  88. FLORIAN@NEOTERIC.COM
  89.