Géographie généralisée

Soit GG = { <G, b> | P1 a une stratégie gagnante sur le graphe g en commencant sur le sommet b dans une partie du jeu de géographie généralisé. }. On montre que GG est dans PSPACE en introduisant l'algorithme suivant, d'exécution polynomiale.

Entrée : <G, nstart>

1. Mesurer l'arité de sortie de nstart. Si cette arité est 0 renvoyer « perdu ».
2. Construire une liste des nœuds accessibles depuis nstart: L = n1, n2, … , ni.
3. Construire G2 en extrayant nstart et toutes les arêtes qui lui sont reliées de G.
4. Effectuer un appel récursif de paramètre <G2, n> pour chaque n dans L. Ces appels récursifs sont effectués séquentiellement. On ne paye donc que le cout mémoire de l'appel le plus couteux pour l'ensemble des appels récursifs.
5. Si tous ces appels récursifs renvoient « gagné » renvoyer « perdu » (quoi que fasse P1 son adversaire peut gagner). Sinon renvoyer « gagné ».

L'algorithme décide clairement GG. On a de plus une profondeur de récursion maximale de n et le cout mémoire de chaque étape de récursion est linéaire en la taille de l'entrée. La mémoire consommée est donc bien polynomiale en la taille de l'entrée. GG est dans PSPACE.

La preuve suivante est due à David Liechtenstein et Michael Sipser[1].

Nous allons établir que GG est PSPACE dur en réduisant FORMULA-GAME à GG en temps polynomial (on sait que FORMULA-GAME est lui-même PSPACE dur).

Une instance de FORMULA-GAME consiste en une formule booléenne quantifiée (close) φ = ∃x₁ ∀x₂ ∃x₃ …Qx_k(ψ) où Q est soit ∃ soit ∀ (avec alternance entre les quantificateurs ∃ et ∀). Deux joueurs PE et PA s'affrontent en choisissant successivement les valeurs des variables dans l'ordre de leur quantification. PE choisit la valeur des variables quantifiées par un ∃ et PA choisit les autres. On suppose que ψ est en forme normale conjonctive à clauses de taille 3. PE gagne si et seulement si la formule est vrai après toutes les quantifications.

Soit ψ une instance de FORMULA-GAME.

Sans perte de généralité, on suppose que le premier et le dernier quantificateurs sont des ∃. On peut toujours se ramener à ce cas en rajoutant des variables inutiles n'apparaissant pas dans ψ.

On réduit notre instance de FORMULA-GAME à une instance de GG selon le principe illustré par le schéma ci-dessus.

La stratégie optimale de P1 correspondra à celle de PE, et celle de P2 à celle de PA.

La chaîne verticale de gauche correspond au processus de choix des valeurs des variables. Le choix du chemin de gauche ou de droite dans chaque mini-tructure en diamant correspond au choix de la valeur d'une variable. Étant donné que le premier quantificateur est un ∃, PE joue en premier. Il faut que PE joue au début des diamants correspondant à des quantifications ∃ et PA au début des autres. Étant donné que le dernier quantificateur est universel, c'est au tour de P1 de jouer quand on sort du dernier diamant (il correspond à PE). P1 amène le jeu en c puis c'est à P2 de jouer.

On rappel qu'a ce stade dans FORMULA-GAME PE gagne si la formule est vraie et PA gagne si elle est fausse.

Si la formule est fausse (avec la valuation correspondant aux choix de chemins qui ont été faits), il suffit à P2 de choisir un chemin menant à une clause non satisfaite. P1 ne pourra alors que choisir un chemin menant à un littéral valué « faux », et laissera donc un dernier coup à P2 qui gagne la partie. Donc si PA gagne dans l'instance de FORMULA-GAME, P2 gagne dans notre instance de GG.

De même, si la formule est vrai alors quoi que choisisse P2 il a amené P1 dans une clause « vraie ». Ce dernier peut donc choisir un chemin menant à un littéral valué à vrai et gagne la partie.

Donc si PE gagne dans l'instance de FORMULA-GAME, P1 gagne dans notre instance de GG.

On a bien réduit l'instance donnée de FORMULA-GAME à une instance de GG par un procédé polynomial.

Donc GG est PSPACE dur.

Étant donné que GG est PSPACE et que planar GG est obtenu par une restriction des instances de GG, planar GG est dans PSPACE. Il nous reste à prouver que Planar GG est PSPACE dur. On prouve cela en reduisant FORMULA-GAME à Planar GG en passant par GG.

Partant d'une instance de FORMULA-GAME que nous avons déjà réduite à une instance de GG, on dessine le graphe de sorte que trois arêtes ne se croisent jamais en un point et que deux arêtes qui se croisent ne soient jamais utilisées dans la même partie. Cela n'est pas possible en général mais le devient dans le cas des graphes obtenus par la réduction de FORMULA-GAME à GG que nous avons décrit précédemment. Nous remplacons ensuite chaque croisement par la construction présentée dans le schéma ci-dessous.

Le résultat est bien un graphe planaire. Une simple étude des cas possible montre qu'il n'est pas possible de « tourner » lorsqu'on emprunte cette structure de croisement sans perdre en très peu de coups. De plus, c'est bien au bon joueur de jouer quand on quitte cette structure.

Une partie jouée parfaitement sur le nouveau graphe ainsi obtenu aura donc le même résultat que sur le graphe obtenu en sortie de réduction depuis FORMULA-GAME.

Cette réduction est évidemment polynomiale. Planar GG est donc PSPACE complet.