home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / theory / 2763 < prev    next >
Encoding:
Text File  |  1992-12-28  |  2.1 KB  |  56 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!wupost!darwin.sura.net!ra!AIC.NRL.Navy.Mil!hoey
  3. From: hoey@AIC.NRL.Navy.Mil (Dan Hoey)
  4. Subject: Re: Real Numbers vs. Rational Numbers?
  5. Message-ID: <9212281124.hoey@aic.nrl.navy.mil>
  6. Sender: usenet@ra.nrl.navy.mil
  7. Organization: Naval Research Laboratory, Washington, DC
  8. References: <1992Dec16.095412.19570@tom.rz.uni-passau.de> <1992Dec17.114502@di.epfl.ch> <1277@zogwarg.etl.army.mil> <1992Dec24.094657.20379@ringer.cs.utsa.edu>
  9. Date: Mon, 28 Dec 1992 16:24:49 GMT
  10. Lines: 44
  11.  
  12. I wrote:
  13.  
  14. >One interesting complexity non-result is the open question:
  15.  
  16. >    Is the travelling salesman problem with cities on an integer
  17. >    lattice in NP?
  18.  
  19. >The numbers are non only real, but algebraic.  Not only algebraic, but
  20. >constructible!
  21.  
  22. And djimenez@ringer.cs.utsa.edu (Daniel Jimenez) replied:
  23.  
  24. > Hmm.  I think you mean P, not NP (obviously it's in NP).
  25.  
  26. No, I meant NP.  And it is sufficiently nonobvious to be a decades-old
  27. open problem.
  28.  
  29. The hard part about showing this is in NP is the problem of finding
  30. which of two candidate tours is shorter.  In particular, the problem
  31.  
  32.     Given two sets {a1, ..., an} and {b1, ..., bn} of positive
  33.     integers, determine whether
  34.  
  35.     sqrt(a1)+sqrt(a2)+...+sqrt(an) > sqrt(b1)+sqrt(b2)+...+sqrt(bn)
  36.  
  37. is not known to be in NP or co-NP.  If you have any good way of
  38. showing how a NDTM can determine that question in polynomial time, you
  39. should publish it.  You may, if you wish, provide a method that only
  40. works when each of the ai and bi is the sum of two squares.  (If that
  41. helps, the result will be even more amazing.)
  42.  
  43. > Anyway, it seems like this problem is NP-complete....
  44.  
  45. It is well known as an NP-hard problem.  In fact, given n points in
  46. the integer lattice, the question of whether there exists a
  47. Hamiltonian circuit of length n--i.e., consisting of unit-length
  48. edges--is known to be NP-complete.  This is how it is shown that
  49. Euclidean TSP is NP-complete.
  50.  
  51. I don't have it with me, but I believe you will find all of this in
  52. _The_Traveling_Salesman_Problem_, Lawler et. al. (Eds.), Wiley, '85.
  53.  
  54. Dan Hoey
  55. Hoey@AIC.NRL.Navy.Mil
  56.