Re: Real Numbers vs. Rational Numbers?

Article View: comp.theory

Article #1683

#1683

From: Daniel Jimenez
Date: Thu, 24 Dec 1992 09:46

16 lines
1194 bytes

In article <1277@zogwarg.etl.army.mil> hoey@zogwarg.etl.army.mil (Dan Hoey) writes:
>One interesting complexity non-result is the open question:
>
>    Is the travelling salesman problem with cities on an integer
>    lattice in NP?
>
>The numbers are non only real, but algebraic.  Not only algebraic, but
>constructible!

Hmm.  I think you mean P, not NP (obviously it's in NP).  Anyway, it seems
like this problem is NP-complete, since you could use it to get 
arbitrarily close approximations to the "real" (pun intended) TSP.
-- 
Daniel Jimenez                     djimenez@ringer.cs.utsa.edu
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
"                             " -- John Cage

Technical Details

Message-ID: <1992Dec24.094657.20379@ringer.cs.utsa.edu>

Path: arc1-ca.pugleaf.net!sparky!uunet!usc!sdd.hp.com!swrinde!ringer!djimenez

References: <1992Dec16.095412.19570@tom.rz.uni-passau.de> <1992Dec17.114502@di.epfl.ch> <1277@zogwarg.etl.army.mil>

Show Full Headers

Complete Article Headers

Newsgroups: comp.theory
Path: arc1-ca.pugleaf.net!sparky!uunet!usc!sdd.hp.com!swrinde!ringer!djimenez
From: djimenez@ringer.cs.utsa.edu (Daniel Jimenez)
Subject: Re: Real Numbers vs. Rational Numbers?
Message-ID: <1992Dec24.094657.20379@ringer.cs.utsa.edu>
Organization: University of Texas at San Antonio
References: <1992Dec16.095412.19570@tom.rz.uni-passau.de> <1992Dec17.114502@di.epfl.ch> <1277@zogwarg.etl.army.mil>
Date: Thu, 24 Dec 1992 09:46:57 GMT
Lines: 16

Reply to Parent Message