Is this version of the Hanoi towers problem NP-complete?

Question

This was really inspired by Solitaire, but a few people reacted with ``oh, it's like the towers of Hanoi, isn't it?'' so I'll try to pose the problem in terms of discs here.

Let's start. There are n disks on the real line, one of size 1 at position $x_1$, one of size 2 at position $x_2$, ..., and one of size n at position $x_n$. Your goal is to make a tower with all n discs, consuming as little energy as possible in the process. You are allowed to move a tower whose base is a disk of size k only on top of the disk with size k+1 (which may be the top of another mini-tower). The energy you consume to perform such a move is the distance traveled by the moved mini-tower. For example, the energy consumed by the first move is $|x_k-x_{k+1}|$.

Now, you'd like to write a program that tells you whether the energy you have is enough to perform the task. It just needs to say Y or N. (If the answer is Y, then clearly the list of moves is proof enough that the answer is correct, so the problem is NP. If the answer is N, there's no point in even attempting the task---you are too tired.)

What's the fastest such program you can find? Is the problem NP-complete? If it helps, consider a simplifications that restrict $x_k$'s to be rational, integers, integers in a certain range, etc.

Here's an upper bound: $O(n2^n)$. Represent the initial state by the list $x_1$, $x_2$ ,... ,$x_n$. A move affects the state by deleting a number in this list and the energy consumed by the move is the absolute difference between the deleted number and the number coming after. Clearly there are $2^n$ states with at most $n$ moves each. (See my blog post for an example run of this algorithm if it's not clear. The description there is in terms of cards.)

Note: Some of the comments below refer to older versions of the questions. See the history of edits if they seem confusing.

Answer 1

Here's a polynomial time solution given to me by Javi Gomez. Let (i,j) with $i\le j$ represent the situation where disks i, i+1, ..., j are on top of each other in position $x_j$, and let E(i,j) represent the energy needed to obtain that configuration. Clearly E(i,i) is zero for all i. Also, $E(i,j)=\min_k E(i,k)+E(k+1,j)+|x_k-x_j|$. What we want is E(1,n).

(I made this a community wiki since the answer wasn't really found by me. Feel free to edit.)

Answer 2

You said that "If the answer is Y, then clearly the list of moves is proof enough that the answer is correct, so the problem is NP". My question is, can you enumerate the list of moves in polynomial time on a nondeterministic TM ? I would say no. Actually, to enumerate all the moves, you require exponential space, regardless of the type of approach you use: deterministic or nondeterministic. Therefore, your problem is not in NP.