« Pierres » la complexité du jeu

Question

Je suis en train de trouver la classe de complexité de trouver une stratégie gagnante pour le premier joueur dans le jeu suivant:

intance du jeu 'Stones est:

• ensemble fini $ X $
• relation $ R \ subseteq X ^ 3 $
• set $ Y \ X $ subseteq et le noeud $ f \ in X $

A la place, nous pierre de beggining dans chaque élément de $ Y $. Chaque joueur à son tour peut déplacer la pierre de $ x $ à $ z $ IFF. \ $ Existe y.R (x, y, z) \ wedge y \ a \ pierre \ mis \ in \ it $. Joueur qui place pierre $ f $ gagne.

Je pense qu'il est $ PSPACE- complet $, mais je tentais de proove depuis un certain temps, et je court d'idées.

Je ne vais pas mentir, il tâche de devoirs pour ma classe de complexité. Toute aide sera très appréciée.

Answer 1

Le jeu est en fait une instance de deux personnes jeu Pebble , comme @HendrikJan a souligné, et est donc avéré être $ $ de EXPTIME-complet. Ce qui suit est un résumé basé sur une preuve par Kasai, Adachi et Iwata dans SICOMP 8 (4).

Pour commencer, il est assez évident que le jeu est en $ EXPTIME $ - nous pouvons simplement vérifier tous les jeux possibles et voir s'il y a une stratégie gagnante. Pour proove il est $ EXPTIME dur $ est un peu plus difficile.

Nous avons d'abord besoin de connaître la notion de (ou distributeurs automatiques de billets pour faire court) machines Alternance de Turing. Nous allons resserrer davantage la définition pour obtenir ce qu'on appelle ATM standard :

Nous disons un M ATM $ est standard si

1. $ M $ n'a qu'une seule bande de travail avec la tête initialisé à la première cellule de la bande,
2. si une configuration $ C $ de $ M $ est existentiel (universel), alors toutes les configurations $ C \ » en Next_M (C) $ est universel (existentiel),
3. l'état initial est existentielle et l'état d'accepter est universelle, et
4. $ Next_M (C) = \ emptyset $ si et seulement si $ C $ est une configuration accepter.

Où Next_M $ (C) $ Les deontes ensemble de configurations possibles après un mouvement à partir de la configuration $ C $

Maintenant, il vient encore deux lemmes importants éprouvés par Chandra, Kozen et Stockmayer Journal de l'ACM 28 (1) :

---

Lemme 1

Pour chaque $ S (n) \ geq log (n) $, si $ L \ à ASPACE (S (n)) $, puis $ L $ est accepté par une norme ATM dans espace $ S (n) $.

---

Lemme 2

$ EXPTIME = APSPACE $

---

Avoir ces deux à l'esprit, nous voyons maintenant que, compte tenu d'une norme ATM M $ = (Q, \ Sigma, \ Gamma, \ delta, b, q_1, q_a, U) $ tel que seulement $ p (n) $ cellules sont disponible sur la bande de travail pour quelque $ polynôme $ p n $ $, et un mot $ w = W_1 w_2 ... w_n $, nous avons besoin de construire, dans l'espace logarythmic, une instance de jeu de galets $ G $ tel que $ w $ est accepté par $ M $ IFF. premier joueur a stratégie gagnante de $ G $.

Pour ce faire, nous aurons besoin

1. ensemble de champs $ X $ consistant en

   • champs représentant l'état de la bande de travail ($ \ {1..p (n) \} \ times Gamma $)
   • champs représentant l'état actuel de la machine et des têtes de $ (il Q \ times \ {1..n \} \ times \ {1..p (n) \} $)
   • champs représentant des transitions de bande de travail ($ Q \ times \ {1..n \} \ times \ {1..p (n) \} \ times Gamma ^ 2) $
   • trois champs supplémentaires s_1 $, s_2, t $ pour assurer que le joueur gagne le jeu correct

2. Set $ ??R $ de règles qui se traduit par $ \ delta $ dans notre jeu:

   • Pour chaque élément de $ Q \ times \ {1..n \} \ times \ {1..p (n) \} $ si $ \ delta (q, w_i, a) $ contient $ (q » , a '(d', d '')), a \ neq un '$ alors cette transition peut être codé avec les règles suivantes:
     • $ ([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 '']) $
   • Pour chaque élément de $ Q \ times \ {1..n \} \ times \ {1..p (n) \} $ si $ \ delta (q, w_i, a) $ contient $ (q » , a, (d », d '')) $ nous avons juste besoin d'une règle:
     • $ ([q, i, l], [l, a], [q, i + d », l + d '']) $
   • Enfin, nous devons avoir des règles « finisseurs jeu »:
     • pour chaque $ i $ et $ l $ devrait être la règle $ ([q_a, i, l], s_1, s_2) $
     • nous ajoutons également la règle $ (s_2, s_1, t) $

3. Et pour commencer le jeu correctement nous avons besoin de l'ensemble $ S = \ {[q_1,1,1], s_1 \} \ cup \ {[l, b] | 1 \ leq l \ leq p (n) \} $, ce qui signifie que nous sommes dans un état initiall, les deux têtes sont à la beggining des bandes et la bande de travail est vide.

De là, la preuve du fait que $ w $ est accepté par $ M $ IFF. premier joueur a une stratégie gagnante en $ G $ devrait être Pretsimple ty.