6
$\begingroup$

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

$\endgroup$

2 Answers 2

6
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ @Sean: Nice idea! Essentially the same as Johan's, I think. $\endgroup$ Mar 13, 2012 at 15:33
  • $\begingroup$ Yes. I think we both posted at about the same time. $\endgroup$ Mar 13, 2012 at 15:58
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice! Essentially the same as Sean's, I think. $\endgroup$ Mar 13, 2012 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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