Komplexität eines Switch-Netzwerkproblems

Ein Switch-Netzwerk (der Name wird erfunden) besteht aus drei Arten von Knoten:

• ein Startknoten
• ein Endknoten
• ein oder mehrere Vermittlungsknoten

Der Vermittlungsknoten hat 3 Ausgänge: Links, Oben, Rechts; hat zwei Zustände L und R und einen Zielzustand TL oder TR . Jeder Schalter kann mit den folgenden Regeln durchlaufen werden:

• immer von links nach oben; der Zustand des Schalters wechselt zu L
• immer von rechts nach oben; der Zustand des Schalters wechselt auf R
• nur von oben nach links, wenn sich der Schalter im Zustand L befindet; Der Zustand ändert sich nicht
• von oben nach rechts, wenn sich der Schalter im Zustand R befindet; Der Zustand ändert sich nicht
• niemals von links nach rechts oder von rechts nach links

Abbildung 1. Vermittlungsknoten in Zustand L mit Zielzustand TR

Diese Eigenschaften gelten auch:

• 0, 1 oder 2 der Ausgänge eines Schalters können isoliert werden (nicht mit einem anderen Schalter verbunden);
• Ein Pfad kann einen Schalter nur "berühren" , um seinen Status zu ändern: von links eingeben und von links beenden oder von rechts eingeben und von rechts beenden;
• Es gibt keine Einschränkung, wie oft ein Schalter bewegt / berührt werden darf.

Das Entscheidungsproblem lautet: "Existiert ein Pfad vom Startknoten zum Endknoten, sodass alle Endzustände der Switches mit dem entsprechenden Zielzustand übereinstimmen?"

Offensichtlich müssen alle Schalter, die sich anfänglich nicht in ihrem Zielzustand befinden, mindestens einmal überfahren (oder berührt) werden.

Dies ist eine kurze Darstellung eines einfachen Netzwerks (erstellt mit Excel ... ich mache ein besseres):

Eine triviale Lösung ist:

S -> 1 -> 2 -> 3 -> 2 -> E -> 1 -> E

EDIT 2:

1. Ist dieses Problem bekannt? ---> Sie gaben mir den guten Hinweis auf die Hearn-These (Constraint Graphs);

$NPSPACE = PSPACE$

$\mathsf{NP}$

$\mathsf{NP\text{-}complete}$

Das Problem ist zumindest NP-schwer, durch eine Reduzierung von 3-SAT.

Betrachten wir zunächst das Problem, einen Weg von der Suche nach Beginn an den Ausgang des folgenden gerichteten Graphen mit der Einschränkung , dass kein Pfad (Quadrat) Knoten einer Klausel alle drei besuchen:

$(X1 \lor X2 \lor X3)\land(X1\lor\neg X2\lor X4)$

Wir transformieren diese Graphen in ein Switch-Netzwerk. Dafür verwenden wir drei Gadgets:

1. Jeder Kreisknoten und jede bidirektionale Kante wird zu einem Draht , der die Verbindungen zwischen den Schaltern herstellt.
2. Jede gerichtete Kante wird zu einem Einweg- Gadget, das aus einem einzelnen Schalter besteht (siehe unten).
3. Jeder quadratische Knoten repräsentiert einen der drei Schalter, die Teil eines Klausel- Gadgets sind (siehe unten).

In den folgenden Abbildungen sind Schalter als zwei ankommende Pfeile dargestellt, von denen einer gestrichelt (deaktiviert) ist. Die Zielrichtung wird mit einem schwarzen Kreis gezeichnet (so dass sich der durchgezogene Pfeil eventuell auf der Seite des Kreises befinden muss).

Anmerkung: Wir werden Fettdruck verwenden , um den Ausgang des Diagramms von den Ausgängen der Minianwendungen zu unterscheiden .

$A$$B$$B$$A$$X1$$X2$$X3$$X1'$$X2'$$X3'$

Denken Sie daran, dass für das ursprüngliche Diagramm die Suche nach einem Pfad, der zum Ausgang führte und nicht alle drei quadratischen Knoten einer Klausel besuchte, NP-vollständig war. Betrachten Sie nun das Problem, den Ausgang des transformierten Graphen zu erreichen, ohne sich um die Zielpositionen der Schalter zu kümmern.

Beachten Sie, dass jeder Pfad, der eine Lösung für das ursprüngliche Diagrammproblem darstellt, auch eine Lösung für das transformierte Diagramm ist. Nehmen wir also an, ein Pfad für das transformierte Diagramm ist keine Lösung für das ursprüngliche Diagramm. Dies kann in zwei Fällen passieren:

1. $B$$A$
2. Ein Pfad durchläuft alle drei Pfade eines Klausel- Gadgets.

Im ersten Fall muss das Einweg- Gadget zuerst in die vorgesehene Richtung durchlaufen worden sein. In diesem Fall hätte der Pfad es genauso gut vermeiden können, es an erster Stelle zu durchlaufen.

Betrachten Sie also den zweiten Fall, in dem der Pfad alle drei Schalter eines Klausel- Gadgets durchläuft . In diesem Fall werden alle drei Schalter des Geräts umgedreht (siehe unten). Hier nutzen wir die Zielpositionen. Beachten Sie, dass das graue Rückgrat des Klausel- Gadgets nicht mehr erreicht werden kann, was bedeutet, dass die Schalter nicht mehr auf ihre Zielpositionen gerichtet werden können. In diesem Fall kann dieses Klausel- Gadget nicht wiederhergestellt werden.

Es bleibt zu zeigen, dass für jede Lösung des ursprünglichen Diagrammproblems die Schalter des transformierten Diagramms in ihre Zielposition gebracht werden können. Dazu nutzen wir die Tatsache, dass der Ausgangsdraht nur erreicht werden kann, wenn es eine Lösung gibt oder ein Klausel-Gadget nicht mehr wiederherstellbar ist.

Um die Schalter in ihre Zielposition zu bringen, können wir jetzt zusätzliche Einweg- Gadgets vom Ausgangskabel zum Eingang jedes vorhandenen Einweg- Gadgets sowie zu den drei Ausgangskabeln aller Klausel- Gadgets hinzufügen . Sobald der Token den Ausgang erreicht , können alle zusätzlichen Einweg- Gadgets überquert (und dadurch in ihre Zielposition gebracht) und die verbleibenden Schalter in ihre Zielposition gebracht werden (es sei denn, es gibt eine nicht behebbare Klausel). Schließlich kann der Spielstein zum Ausgang zurückkehren und das Rätsel ist gelöst.

Wir möchten darauf hinweisen , dass Klausel- Minianwendungen nur wiederhergestellt werden können, wenn sie über einen nicht überquerten Exit eingegeben werden. Aufgrund der Einweg- Minianwendungen, die zwischen Klausel- Minianwendungen und der nächsten Variablen platziert sind, kann dies erst geschehen, wenn die Ausgangsleitung erreicht ist.

Daher ist das Switch-Netzwerk-Problem NP-schwer.

Es ist immer noch unklar, ob das Problem NP- oder PSPACE-schwer ist. Eine Reduzierung der NP-Härte beim Aufbau eines planaren Switch-Netzwerks hat große Auswirkungen auf eingeschränkte Varianten von Sokoban, da alle Switches dem folgenden Sokoban-Gadget entsprechen.