🚀 go-pugleaf

I wrote:

>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!

And djimenez@ringer.cs.utsa.edu (Daniel Jimenez) replied:

> Hmm.  I think you mean P, not NP (obviously it's in NP).

No, I meant NP.  And it is sufficiently nonobvious to be a decades-old
open problem.

The hard part about showing this is in NP is the problem of finding
which of two candidate tours is shorter.  In particular, the problem

    Given two sets {a1, ..., an} and {b1, ..., bn} of positive
    integers, determine whether

    sqrt(a1)+sqrt(a2)+...+sqrt(an) > sqrt(b1)+sqrt(b2)+...+sqrt(bn)

is not known to be in NP or co-NP.  If you have any good way of
showing how a NDTM can determine that question in polynomial time, you
should publish it.  You may, if you wish, provide a method that only
works when each of the ai and bi is the sum of two squares.  (If that
helps, the result will be even more amazing.)

> Anyway, it seems like this problem is NP-complete....

It is well known as an NP-hard problem.  In fact, given n points in
the integer lattice, the question of whether there exists a
Hamiltonian circuit of length n--i.e., consisting of unit-length
edges--is known to be NP-complete.  This is how it is shown that
Euclidean TSP is NP-complete.

I don't have it with me, but I believe you will find all of this in
_The_Traveling_Salesman_Problem_, Lawler et. al. (Eds.), Wiley, '85.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil