Newsgroups: comp.theory
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 23 Dec 92 18:45:31 GMT
Subject: Re: Real Numbers vs. Rational Numbers?

dider...@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