Re: Real Numbers vs. Rational Numbers?

Article View: comp.theory

Article #1682

#1682

From: Dan Hoey
Date: Wed, 23 Dec 1992 18:45

17 lines
986 bytes

diderich@di.epfl.ch (Claude Diderich) writes:

>I asked myself some time ago the same question (e.g. are Turing
>machines computing on real numbers equvalent on ones computing only
>on rationals), but I was unable to find any answer. I was especially
>intersted in complexity theoretical results.

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!

Dan Hoey
Hoey@AIC.NRL.Navy.Mil

Technical Details

Message-ID: <1277@zogwarg.etl.army.mil>

Path: arc1-ca.pugleaf.net!sparky!uunet!dtix!relay!relay2!tecsun1!zogwarg!hoey

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

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!sparky!uunet!dtix!relay!relay2!tecsun1!zogwarg!hoey
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Newsgroups: comp.theory
Subject: Re: Real Numbers vs. Rational Numbers?
Message-ID: <1277@zogwarg.etl.army.mil>
Date: 23 Dec 92 18:45:31 GMT
References: <1992Dec16.095412.19570@tom.rz.uni-passau.de> <1992Dec17.114502@di.epfl.ch>
Organization: Naval Research Laboratory, Washington, DC
Lines: 17

Reply to Parent Message