sum of like indices in circular lists

Question

Consider the following problem:

Let a $k$-wheel be defined as an indexed circularly linked list of $k$ integers. For example…

{3, 4, 9, -1, 6}

…is a 5-wheel with 3 at position 0, 4 at position 1, and so on. A wheel supports the operation of rotation, so that a one-step rotation would turn the above wheel into…

{6, 3, 4, 9, -1}

…now with 6 at position 0, 3 at position 1, and so on. Let $W_{N_k}$ be an ordered set of $N$ distinct $k$-wheels. Given some $W_{N_k}$ and some integer $t$, find a series of rotations such that…

$$\forall\ 0 \leq i < k, \sum_{N \in W} N_i = t$$

In other words, if you laid out the wheels as a matrix, the sum of every column would be $t$. Assume that $W_{N_k}$ is constructed so that the solution is unique up to rotations of every element (i.e., there are exactly $k$ unique solutions that consist of taking one solution, then rotating every wheel in $W$ by the same number of steps).

The trivial solution to this problem involves simply checking every possible rotation. Here is some pseudocode for that:

function solve(wheels, index)
    if wheels are solved:
        return true
    if index >= wheels.num_wheels:
        return false
    for each position 1..k:
        if solve(index + 1) is true:
            return true
        else:
            rotate wheels[index] by 1

solve(wheels, 0)

This is a pretty slow solution (something like $O(k^n)$). I'm wondering if it is possible to do this problem faster, and also if there is a name for it.

Answer 1

For most of this answer, I discuss the decision version of the problem, in which an instance having at most one solution is given (the "promise"), and you have to decide whether it has any solutions or none.

You can reduce PARTITION to your problem (exercise). (PARTITION is the problem of determining whether a set of integers can be partitioned into two parts with equal sum.) Admittedly, this doesn't necessarily satisfy the condition that the solution be unique.

With some more work, you can (directly) reduce SAT to (the decision version of) your problem, and perhaps that can be done in such a way so that if the SAT instance has a unique solution, then so does the resulting instance of your problem. In that case, we get that the decision version is not solvable in polytime unless NP=RP, which is considered unlikely.

Note that if the decision version (more accurately, the promise version) of the problem is not solvable in polytime, then no algorithm can solve all YES instances in polytime: if it did, you could run it up to its allotted running time, and check the solution (if the algorithm stopped in time).