home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / logic / 2162 < prev    next >
Encoding:
Text File  |  1992-11-23  |  1.8 KB  |  37 lines
  1. Newsgroups: sci.logic
  2. Path: sparky!uunet!secapl!Cookie!frank
  3. From: frank@Cookie.secapl.com (Frank Adams)
  4. Subject: Re: Logic and Mathematicians
  5. Message-ID: <1992Nov23.161422.19031@Cookie.secapl.com>
  6. Date: Mon, 23 Nov 1992 16:14:22 GMT
  7. References: <56452@dime.cs.umass.edu> <1992Nov21.185205.3566@dorsai.com>
  8. Organization: Security APL, Inc.
  9. Lines: 26
  10.  
  11. In article <1992Nov21.185205.3566@dorsai.com> mutation@dorsai.com (Florian Lengyel) writes:
  12. >Computing processes seem too fundamental to me, too much a part of the
  13. >way mathematics and meta-mathematics is conducted to begin with ...
  14. >Computing processes, which include the computation of inferences, are  
  15. >absolute, in other words, so they should not be suceptible to varying 
  16. >interpretations of set theory that would lead to such grossly different 
  17. >computational outcomes as P = NP under one interpretation and P <> NP 
  18. >under another.
  19.  
  20. But non-standard interpretations of ZFC often have non-standard integers.
  21. It is quite possible for an algorithm to "halt" in time n^K, where K is a
  22. non-standard integer in such a model, but not to halt in time n^k for any
  23. actual integer k.
  24.  
  25. If one could show P=NP in a model of ZFC (or more likely PA) which could be
  26. shown to have non-standard integers, while showing P < NP in a model which
  27. did not appear to require non-standard integers, that would be strong
  28. evidence for P < NP.  Depending on the details, a proof (on the
  29. meta-theoretic level) might even be possible.
  30.  
  31. It is also possible that P < NP, but that no proof is available in any
  32. system we can accept.  More specifically, P < NP may be independent of ZFC,
  33. but we will not be able to prove it.  This is possible for any unsolved
  34. problem, of course, but it seems more likely for unsolved problems in
  35. complexity theory (and even more so in computability and set theory) than in
  36. most areas.
  37.