home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / theory / 2755 < prev    next >
Encoding:
Text File  |  1992-12-24  |  1.1 KB  |  27 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!usc!sdd.hp.com!swrinde!ringer!djimenez
  3. From: djimenez@ringer.cs.utsa.edu (Daniel Jimenez)
  4. Subject: Re: Real Numbers vs. Rational Numbers?
  5. Message-ID: <1992Dec24.094657.20379@ringer.cs.utsa.edu>
  6. Organization: University of Texas at San Antonio
  7. References: <1992Dec16.095412.19570@tom.rz.uni-passau.de> <1992Dec17.114502@di.epfl.ch> <1277@zogwarg.etl.army.mil>
  8. Date: Thu, 24 Dec 1992 09:46:57 GMT
  9. Lines: 16
  10.  
  11. In article <1277@zogwarg.etl.army.mil> hoey@zogwarg.etl.army.mil (Dan Hoey) writes:
  12. >One interesting complexity non-result is the open question:
  13. >
  14. >    Is the travelling salesman problem with cities on an integer
  15. >    lattice in NP?
  16. >
  17. >The numbers are non only real, but algebraic.  Not only algebraic, but
  18. >constructible!
  19.  
  20. Hmm.  I think you mean P, not NP (obviously it's in NP).  Anyway, it seems
  21. like this problem is NP-complete, since you could use it to get 
  22. arbitrarily close approximations to the "real" (pun intended) TSP.
  23. -- 
  24. Daniel Jimenez                     djimenez@ringer.cs.utsa.edu
  25. "I've so much music in my head" -- Maurice Ravel, shortly before his death.
  26. "                             " -- John Cage
  27.