Komplexität des Spiels „Steine“.

Question

Ich versuche, die Komplexitätsklasse für die Gewinnstrategie für den ersten Spieler im folgenden Spiel zu finden:

Instanz des Spiels „Stones“ ist:

• endliche Menge $X$
• Relation $R \subseteq X^3$
• setze $Y \subseteq X$ und Knoten $f \in X$

Zu Beginn platzieren wir Steine ​​in jedem Element von $Y$.Jeder Spieler kann in seinem Zug einen Stein von $x$ nach $z$ bewegen, wenn.$\exists y.R(x, y, z) \Keil y\ hat\ Stein\ darin platziert$.Der Spieler, der einen Stein in $f$ platziert, gewinnt.

Ich denke, es ist $PSPACE-vollständig$, aber ich habe einige Zeit versucht, dies zu beweisen, und mir sind die Ideen ausgegangen.

Ich werde nicht lügen, es ist eine Hausaufgabe für meinen Komplexitätskurs.Jede Hilfe wird sehr geschätzt.

Answer 1

Das Spiel ist tatsächlich eine Instanz von Kieselspiel für zwei Personen, wie @HendrikJan betonte, und ist daher nachweislich $EXPTIME-vollständig$.Das Folgende ist eine Zusammenfassung, die auf einem Beweis von Kasai, Adachi und Iwata in SICOMP 8 (4) basiert.

Zunächst einmal ist es ziemlich offensichtlich, dass das Spiel in $EXPTIME$ ist – wir können einfach alle möglichen Spiele überprüfen und sehen, ob es eine Gewinnstrategie gibt.Zu beweisen, dass es $EXPTIME-schwer ist, ist etwas anspruchsvoller.

Zuerst müssen wir den Begriff kennen Alternierende Turingmaschinen (oder kurz Geldautomaten).Wir werden die Definition noch weiter verschärfen, um so genannt zu werden Standard-Geldautomat:

Wir sagen, ein Geldautomat $M$ ist Standard Wenn

1. $M$ hat nur ein Arbeitsband, dessen Kopf auf die erste Zelle des Bandes initialisiert ist.
2. Wenn eine Konfiguration $C$ von $M$ existentiell (universell) ist, dann ist jede Konfiguration $C‘ \in Next_M(C)$ universell (existentiell),
3. der Ausgangszustand ist existenziell und der akzeptierende Zustand ist universell, und
4. $Next_M(C) = \emptyset$ genau dann, wenn $C$ eine akzeptierende Konfiguration ist.

Wobei $Next_M(C)$ die Menge möglicher Konfigurationen nach einem Zug ausgehend von der Konfiguration $C$ beschreibt

Nun kommen zwei wichtige Lemmata hinzu, die von Chandra, Kozen und Stockmayer bewiesen wurden Zeitschrift der ACM 28(1):

---

Lemma 1

Für jedes $S(n) \geq log (n)$, wenn $L \in ASPACE(S(n))$, dann wird $L$ von a akzeptiert Standard Geldautomat im Raum $S(n)$.

---

Lemma 2

$EXPTIME = APSPACE$

---

Nachdem wir diese beiden im Vordergrund sehen, sehen wir jetzt, dass bei einem Standard atm $ m = (q, sigma, gamma, delta, b, q_1, q_a, u) $ so dass nur $ p (n) $ Zellen sind Erhältlich auf dem Arbeitsband für ein Polynom $ p $ in $ n $ und ein Wort $ w = w_1 W_2 ...w_n$, müssen wir im logarythmischen Raum eine Instanz des Kieselspiels $G$ konstruieren, so dass $w$ von $M$ genau dann akzeptiert wird.Der erste Spieler hat eine Gewinnstrategie in $G$.

Dazu benötigen wir

1. Menge von Feldern $X$ bestehend aus

   • Felder, die den Zustand des Arbeitsbandes darstellen ($\{1..p(n)\} imes \Gamma$)
   • Felder, die den aktuellen Zustand der Maschine und ihrer Köpfe darstellen ($Q imes \{1..n\} imes \{1..p(n)\}$)
   • Felder, die Arbeitsbandübergänge darstellen ($Q imes \{1..n\} imes \{1..p(n)\} imes \Gamma^2)$
   • drei zusätzliche Felder $s_1, s_2, t$, um sicherzustellen, dass der richtige Spieler das Spiel gewinnt

2. Legen Sie $R$ an Regeln fest, die $\delta$ in unser Spiel übersetzen:

   • Für jedes Element von $Q imes \{1..n\} imes \{1..p(n)\}$, wenn $\delta (q, w_i, a)$ $(q', a' enthält , (d', d'')), a eq a'$, dann kann dieser Übergang mit den folgenden Regeln codiert werden:
     • $([q, i, l], [l, a], [q, i, l, a, a'])$
     • $([l, a], [q, i, l, a, a'], [l, a'])$
     • $([q, i, l, a, a'], [l, a'], [q, i+d', l+d''])$
   • Für jedes Element von $Q imes \{1..n\} imes \{1..p(n)\}$, wenn $\delta (q, w_i, a)$ $(q', a, (d', d''))$ wir brauchen nur eine Regel:
     • $([q, i, l], [l, a], [q, i+d', l+d''])$
   • Schließlich brauchen wir Regeln für den Abschluss des Spiels:
     • Für jedes $i$ und $l$ sollte es die Regel $([q_a, i, l], s_1, s_2)$ geben
     • Wir fügen auch die Regel $(s_2, s_1, t)$ hinzu

3. Und um das Spiel richtig zu starten 1 Leq l Leq P (n) } $, was bedeutet, dass wir im anfänglichen Zustand sind, beide Köpfe am Betteln der Bänder sind und das Arbeitsband leer ist.

Daraus ergibt sich der Beweis dafür, dass $w$ von $M$ genau dann akzeptiert wird.Der erste Spieler hat eine Gewinnstrategie in $G$, sollte ziemlich einfach sein.