Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
I suspect this might be NP-complete, since it doesn't look like we can really tell if a partial solution is going to lead to a correct solution until we set the final wheel... I don't have a proof yet though. I'll add an answer if I think of one. –  Matt Lewis Jan 9 '13 at 16:51
add comment

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

share|improve this answer
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.