Form a $\mathbb{Z}^d$ lattice cycle from given lengths - MathOverflow

Form a $\mathbb{Z}^d$ lattice cycle from given lengths

2012-03-13T12:52:10Z

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.

Answer by Sean Eberhard for Form a $\mathbb{Z}^d$ lattice cycle from given lengths

2012-03-13T14:16:00Z

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?

Answer by Johan Wästlund for Form a $\mathbb{Z}^d$ lattice cycle from given lengths

2012-03-13T14:18:44Z

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.