'Stones' complessità gioco

Question

Sto cercando di trovare la classe di complessità di trovare la strategia vincente per primo giocatore nella partita seguente:

intance di gioco 'Stones' è:

• finito insieme $ X $
• relazione $ R \ subseteq X ^ 3 $
• set $ Y \ subseteq X $ e il nodo $ f \ in X $

Al beggining abbiamo posto in pietra in ogni elemento di $ Y $. Ogni giocatore a sua volta può muovere passi da $ x $ a $ Z $ se e solo se. $ \ Esiste y.R (x, y, z) \ cuneo y \ ha \ pietra \ locale \ in \ esso $. Giocatore che piazza in pietra $ f $ vittorie.

Credo che sia $ $ PSPACE-completo, ma stavo cercando di proove questo per qualche tempo, e corro a corto di idee.

Non voglio mentire, è compito a casa per la mia classe di complessità. Qualsiasi aiuto sarà molto apprezzato.

Answer 1

Il gioco è in realtà un esempio di due persone Pebble gioco , come @HendrikJan ha sottolineato, e come tale è dimostrato di essere $ $ EXPTIME-completo. Quanto segue è una sintesi sulla base di una prova da Kasai, Adachi e Iwata in SICOMP 8 (4).

Per cominciare, è abbastanza evidente che il gioco è in $ EXPTIME $ - possiamo semplicemente visualizzate tutte le possibili giochi e vedere se v'è strategia vincente. Per proove è $ $ EXPTIME-hard è un po 'più impegnativo.

In primo luogo abbiamo bisogno di conoscere la nozione di alternata di Turing macchine (o ATM in breve). Ci sarà ulteriormente stringere la definizione per ottenere i cosiddetti standard di ATM :

Diciamo un bancomat $ M $ è standard se

1. $ M $ ha un solo nastro di lavoro con la testa inizializzata alla prima cella del nastro,
2. se una configurazione di $ C $ di $ M $ è esistenziale (universale), allora ogni configurazione di $ C’\ a Next_M (C) $ è universale (esistenziale),
3. lo stato iniziale è esistenziale e lo stato accettante è universale, e
4. $ Next_M (C) = \ emptyset $ se e solo se $ C $ è una configurazione di accettare.

Dove $ Next_M (C) $ deontes insieme di possibili configurazioni dopo uno spostamento a partire dalla configurazione $ C $

Ora vengono ancora due lemmi importanti provati da Chandra, Kozen e Stockmayer in ufficiale ACM 28 (1) :

---

Lemma 1

Per ogni S (n) \ log $ geq (n) $, se $ L \ a ASPACE (S (n)) $, allora $ L $ è accettato da un standard Bancomat all'interno spazio $ S (n) $.

---

Lemma 2

$ EXPTIME = APSPACE $

---

Avere quei due in mente, ora vediamo che, dato uno standard ATM $ M = (Q, \ Sigma, \ Gamma, \ delta, b, Q_1, Q_A, U) $ tale che solo $ p (n) $ cellule sono disponibili sul nastro di lavoro per qualche polinomio $ p $ in $ n $, e una parola $ w = W_1 w_2 ... w_n $, abbiamo bisogno di costruire, nello spazio logaritmica, un'istanza di ciottoli gioco $ G $ tale che $ w $ è accettato da $ M $ se e solo se. primo giocatore ha strategia vincente in $ G $.

Per fare questo avremo bisogno

1. set di campi $ X $, rappresentati da

   • campi che rappresentano lo stato di nastro di lavoro ($ \ {1..p (n) \} \ times \ gamma $)
   • campi che rappresentano lo stato attuale della macchina e di teste ($ Q \ times \ {1..n \} \ times \ {1..p (n) \} $)
   • campi che rappresentano le transizioni Nastro del lavoro ($ Q \ times \ {1..n \} \ times \ {1..p (n) \} \ times \ gamma ^ 2) $
   • tre campi aggiuntivi $ S_1, s_2, t $ per garantire che corretto giocatore vince la partita

2. Set $ ??R $ di regole che si traduce $ \ delta $ nel nostro gioco:

   • Per ogni elemento di $ Q \ times \ {1..n \} \ times \ {1..p (n) \} $ se $ \ delta (q, w_i, a) $ contiene $ (q' , a '(d', d '')), un \ neq un '$ allora questa transizione può essere codificato con le seguenti regole:
     • $ ([q, i, l], [l, a], [q, I, L, a, a ']) $
     • $ ([l, a], [q, I, L, a, a '], [l, un']) $
     • $ ([q, I, L, a, a '], [l, un'], [q, i + d', l + d '']) $
   • Per ogni elemento di $ Q \ times \ {1..n \} \ times \ {1..p (n) \} $ se $ \ delta (q, w_i, a) $ contiene $ (q' , una, (d', d '')) $ abbiamo bisogno di una sola regola:
     • $ ([q, i, l], [l, a], [q, i + d', l + d '']) $
   • Infine abbiamo bisogno di avere "finisher gioco" regole:
     • per ogni $ i $ e $ l $ ci dovrebbe essere regola $ ([Q_A, I, L], S_1, s_2) $
     • abbiamo anche aggiungere regola $ (s_2, S_1, t) $

3. E per iniziare il gioco correttamente abbiamo bisogno del set $ S = \ {[q_1,1,1], S_1 \} \ tazza \ {[l, b] | 1 \ leq l \ leq p (n) \} $, che denota che siamo in stato initiall, entrambe le teste sono al beggining dei nastri, e il nastro di lavoro è vuota.

Da questo, la prova del fatto che $ w $ è accettato da $ M $ se e solo se. primo giocatore ha una strategia vincente in $ G $ dovrebbe essere pretty semplice.