The Turnpike Problem

We take freeway exits for granted: I have often wondered what would happen if we had to do our regular commutes without the benefit of the huge green signs announcing breathlessly that our exit is 1 mile ....1/2 mile.... 1/4 mile... 500 FEET away.

Suppose it got even worse: not only do we not have exit signs, we don't even know quite where the exits are - sort of like platform 9 3/4 at King's Cross. However mercifully (or sadistically, depending on your point of view), someone supplied us with distances between pairs of exits. Formally, we are given numbers x1, x2, ...x(N * (N-1)/2) and must determine the exits P1, P2, .... PN that yield these inter-exit distances.

Reconstructing the locations of the exits is called The Turnpike Problem. A Google search yields lots of information on this topic: in fact the first link is:

Turnpike not the problem; traffic is

Oh well, never mind....

At any rate, this problem is surprisingly nasty. It occupies the limbo zone between NP-Complete and P, in the company of Graph Isomorphism and Factoring (they used to have a bridge foursome before Primes departed for P-land). It can be reduced to factoring an appropriately chosen polynomial, and so proving it NP-hard would be extremely interesting.

Turnpike reconstruction also comes up in X-ray crystallography and DNA reconstruction. Skiena, Smith and Lemke discuss this problem in some detail and present a backtracking method for solving it.

A Variant: I just saw this on comp.theory:

Suppose that instead of providing the difference between pairs of exits, we were given the sums. Does the problem change significantly ?