home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / theory / 2753 < prev    next >
Encoding:
Internet Message Format  |  1992-12-23  |  959 b 
  1. Path: sparky!uunet!dtix!relay!relay2!tecsun1!zogwarg!hoey
  2. From: hoey@zogwarg.etl.army.mil (Dan Hoey)
  3. Newsgroups: comp.theory
  4. Subject: Re: Real Numbers vs. Rational Numbers?
  5. Message-ID: <1277@zogwarg.etl.army.mil>
  6. Date: 23 Dec 92 18:45:31 GMT
  7. References: <1992Dec16.095412.19570@tom.rz.uni-passau.de> <1992Dec17.114502@di.epfl.ch>
  8. Organization: Naval Research Laboratory, Washington, DC
  9. Lines: 17
  10.  
  11. diderich@di.epfl.ch (Claude Diderich) writes:
  12.  
  13. >I asked myself some time ago the same question (e.g. are Turing
  14. >machines computing on real numbers equvalent on ones computing only
  15. >on rationals), but I was unable to find any answer. I was especially
  16. >intersted in complexity theoretical results.
  17.  
  18. One interesting complexity non-result is the open question:
  19.  
  20.     Is the travelling salesman problem with cities on an integer
  21.     lattice in NP?
  22.  
  23. The numbers are non only real, but algebraic.  Not only algebraic, but
  24. constructible!
  25.  
  26. Dan Hoey
  27. Hoey@AIC.NRL.Navy.Mil
  28.