Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose you are given a list of integer lengths, e.g., $(5,3,2,2,1,1,2,1,1)$. The task is to decide if they can form a closed cycle in $\mathbb{Z}^d$ by connecting segments of those lengths in order, each parallel to a coordinate axis, each connecting two lattice points, each orthogonal to its neighbors. This latter condition forbids connecting two segments collinearly: a $90^\circ$ turn is forced between each pair of segments.

In $\mathbb{Z}^2$, the decision problem is NP-complete, because both the horizontal, and the vertical lengths must partition equally to close: $5+1=2+2+2$ and $3+1=2+1+1$ in the example left below.
          Orthogon
al Cycles
Thus given an even number of integers, interleaving 1's results in a list that can form a cycle in $\mathbb{Z}^2$ iff the given integers may be partitioned into two equal halves. My question is:

Q. Is the decision problem NP-complete in $\mathbb{Z}^d$ for $d \ge 3$?

The choices of which direction to follow at each juncture seem to complicate a reduction from Partition. I feel like I am missing a simple argument here ... I'd appreciate it if anyone could supply it—Thanks!

Addendum. A potentially more interesting question lay behind what I posed above: When might the list of lengths be formed to realize the unknot in $\mathbb{Z}^3$? I'll post that as a separate question if I can see how to formulate it sharply.

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

Suppose you have a machine that solves the problem in $\mathbb{Z}^{d+1}$ quickly, and you want to use it to solve the problem in $\mathbb{Z}^d$. Suppose that your input is a list $(a_1,\ldots,a_k)$ of $k$ integers each of $n$ bits, so that your total input size is $kn$. Feed the list $(a_1,k2^n,a_2,k2^n,a_3,\ldots k2^n,a_k,k(k-1)2^n)$ to your machine. The new input size is $kn + (k-1)(\log k + n) + 2\log k + n$. All the entries $k2^n,k2^n,\ldots,k2^n,k(k-1)2^n$ must apear along the same dimension, so solving this new problem in $\mathbb{Z}^{d+1}$ amounts to solving the original problem in $\mathbb{Z}^d$. Does something like this work?

share|improve this answer
    
@Sean: Nice idea! Essentially the same as Johan's, I think. –  Joseph O'Rourke Mar 13 '12 at 15:33
    
Yes. I think we both posted at about the same time. –  Sean Eberhard Mar 13 '12 at 15:58
add comment

Suppose we are given a sequence $a_1,\dots, a_n$ (input to a partition problem). It seems that this can be encoded as a cycle problem in $\mathbb{Z}^3$ by finding two large numbers $M$ and $N$ and taking the sequence to be $$a_1, M, N, a_2, M, N, \dots, a_n, (n-1)M, (n-1)N.$$ The numbers $M$ and $N$ should be chosen so that the two last terms cannot be canceled in any other way than the obvious one. Then by the orthogonality rule, the only remaining possibility is to let the terms $a_1,\dots,a_n$ go in the third direction, and we are back to the partition problem.

This ought to work also for $d\geq 4$, although admittedly some details remain to be filled in.

share|improve this answer
    
Nice! Essentially the same as Sean's, I think. –  Joseph O'Rourke Mar 13 '12 at 15:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.