Summe gleicher Indizes in kreisförmigen Listen

Betrachten Sie das folgende Problem:

Ein Rad $k$ sei als indizierte kreisförmig verknüpfte Liste von ganzen Zahlen definiert. Zum Beispiel… $k$

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

… Ist ein 5-Rad mit 3 an Position 0, 4 an Position 1 und so weiter. Ein Rad unterstützt den Drehbetrieb, so dass eine einstufige Drehung das obige Rad in…

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

… Jetzt mit 6 an Position 0, 3 an Position 1 und so weiter. Sei eine geordnete Menge von verschiedenen Rädern. Finden Sie bei gegebenem und einer ganzen Zahl eine Reihe von Rotationen, so dass… $W_{N_k}$ $N$ $k$ $W_{N_k}$ $t$

$\forall 0 \leq ich < k, \sum_{N. \in W.} {N.}_{ich} = t$ $\forall\ 0 \leq i < k, \sum_{N \in W} N_i = t$
Mit anderen Worten, wenn Sie die Räder als Matrix auslegen, wäre die Summe jeder Spalte . Angenommen, ist so konstruiert, dass die Lösung bis zu Umdrehungen jedes Elements eindeutig ist (dh es gibt genau eindeutige Lösungen, die darin bestehen, eine Lösung zu nehmen und dann jedes Rad in um die gleiche Anzahl von Schritten zu drehen ). $t$ $W_{N_k}$ $k$ $W$

Die triviale Lösung für dieses Problem besteht darin, einfach jede mögliche Drehung zu überprüfen. Hier ist ein Pseudocode dafür:

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)

Dies ist eine ziemlich langsame Lösung (so etwas wie ). Ich frage mich, ob es möglich ist, dieses Problem schneller zu lösen und ob es einen Namen dafür gibt. $O(k^n)$

algorithms Apis Utilis
quelle

Ich vermute, dass dies NP-vollständig sein könnte, da es nicht so aussieht, als ob wir wirklich sagen können, ob eine Teillösung zu einer korrekten Lösung führen wird, bis wir das endgültige Rad eingestellt haben ... Ich habe jedoch noch keinen Beweis . Ich werde eine Antwort hinzufügen, wenn ich an eine denke.

Matt Lewis

Antworten:

Für den größten Teil dieser Antwort diskutiere ich die Entscheidungsversion des Problems, in der eine Instanz mit höchstens einer Lösung angegeben wird (das "Versprechen"), und Sie müssen entscheiden, ob es irgendwelche Lösungen gibt oder keine.

Sie können PARTITION auf Ihr Problem reduzieren (Übung). (PARTITION ist das Problem, zu bestimmen, ob eine Menge von ganzen Zahlen mit gleicher Summe in zwei Teile aufgeteilt werden kann.) Zugegebenermaßen erfüllt dies nicht unbedingt die Bedingung, dass die Lösung eindeutig ist.

Mit etwas mehr Arbeit können Sie SAT (direkt) auf (die Entscheidungsversion) Ihres Problems reduzieren, und dies kann möglicherweise so erfolgen, dass, wenn die SAT-Instanz eine eindeutige Lösung hat, auch die resultierende Instanz von Ihr Problem. In diesem Fall stellen wir fest, dass die Entscheidungsversion in Polytime nur lösbar ist, wenn NP = RP, was als unwahrscheinlich angesehen wird.

Beachten Sie, dass, wenn die Entscheidungsversion (genauer gesagt die Versprechungsversion) des Problems in Polytime nicht lösbar ist, kein Algorithmus alle YES-Instanzen in Polytime lösen kann: Wenn dies der Fall ist, können Sie es bis zu seiner zugewiesenen Laufzeit ausführen Überprüfen Sie die Lösung (wenn der Algorithmus rechtzeitig gestoppt wurde).

Yuval Filmus
quelle