3 Addendum on what lay behind my question.

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.

2 added 1 characters in body

Suppose you are give 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!

1

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

Suppose you are give 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!