Utilisateur:SCoumes/Brouillon

En théorie de la complexité, Géographie Généralisé est un problème PSPACE complet classique. Il est plus connu sous son nom anglais Generalized Geography et est abrégé GG.

Introduction

A l'origine, Géographie est un jeu particulièrement adapté aux longs trajets en voiture dans lequel deux joueurs énoncent à tour de rôle différents noms de villes. Chaque nom de ville donné doit commencer par la dernière lettre du précédant (à l'exception du premier qui est librement choisit) et il est interdit de donner un nom de ville qui a déjà été employé. Le premier joueur qui ne peut pas donner de nom de ville respectant les contraintes perd la partie et le jeu prend alors fin.

Modélisation par graphe

Le jeu peut être représenté par un graphe orienté dont les noeuds représentent les noms de ville du monde. Une flèche lie le noeud N1 au noeud N2 si et seulement si le nom de ville représenté par le noeud N2 commence par la dernière lettre de celui représenté par le noeud N1. Autrement dit, une flèche représente le fait qu'il est possible de passer d'une ville à une autre en accord avec les règles du jeu. Une partie correspond alors à une marche sur le graphe où les joueurs choisissent chacun leur tour un noeud voisin du noeud actuel qui n'a pas été visité. Le premier joueur qui en est incapable perd la partie. Un exemple illustré avec des noms de villes de l'etat du Michigan (USA) est présenté ci-dessous.

Dans le problème Géographie Généralisé on considère simplement un graphe orienté dont l'un des sommets est spécifié être le sommet de départ (on ne choisit plus la première "ville" librement). Le graphe suivant illustre un exemple d'instance du problème GG.

Jouer une partie

On définit P₁ le joueur qui joue en premier et P₂ le deuxième. On définit de plus N₁, ..., N_n les noeuds du graphe avec N₁ le point d'entrée. Une partie jouée correspond à un chemin maximal ne passant jamais deux fois par le même sommet en commençant au noeud N_1.

Complexité calculatoire

Le problème GG qui consiste étant donné un graphe G et un sommet N₁ à trouver quel joueur (P₁ ou P₂) a une stratégie gagnant est PSPACE complet.

Géographie Généralisé est PSPACE Complet

GG est PSPACE Complet. Cela signifie qu'il est à la fois PSPACE et PSPACE dur. On prouve ces deux affirmations séparément.

Géographie Généralisé est PSPACE.

Démonstration

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'éxé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 noeuds 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.

Géographie généralisé est PSPACE dur.

Démonstration

La preuve suivante est due à David Lichtenstein et Michael Sipser.

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. Etant donné que le premier quantificateur est un ∃, PE joue en premier. Il faut que PE joue au début des diamants corresponants à des quantifications ∃ et PA au début des autres. Etant 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.

Planar GG

Le problème GG restreint aux graphes planaires (Planar GG) est toujours PSPACE complet. La preuve suivant est issue du théorème 3 de .

Démonstration

Etant 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écedement. 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" lorsque 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 évidement polynomiale. Planar GG est donc PSPACE complet.

Graphes plan bipartis d'arité maximale 3

Le problème restreint aux graphes plan biparits d'arité maximale 3 est toujours PSPACE dur. Cela se prouve en remplaçant les sommets d'arité strictement supérieure à trois par des chaines de sommets. Une preuve peut être trouvée dans .

Edge Geography

Il existe une variante de GG nommée EDGE GEOGRAPHY (traduisible par Géographie arête) où, après chaque coup, on efface l’arête qui vient d'être employée mais où on peut passer plusieurs fois par le même nœud. Cela contraste avec GG, qui peut être vu comme effaçant les sommets empruntés à chaque étape. On peut donc considérer que GG est "Sommet Geographie" (EDGE GEOGRAPHY).

EDGE GEOGRAPHY est également PSPACE complet. Cela se prouve en réduisant des formules booléennes quantifiées à des instances de EDGE GEOGRAPHY .

Graphe non orienté

On peut envisager une variante de GG basée sur des graphes non orientés. Fraenkel, Scheinerman, et Ullman ont montré que EDGE GEOGRAPHY non orienté est dans P tandis que GG non orienté est PSPACE complet, même en se restreignant aux graphes plan d'arité maximale 3. Si on se restreint aux graphes bipartis, le problème peut être résolu en temps polynomial.

References

• Michael Sipser, Introduction to the Theory of Computation, PWS, 1997.
• David Lichtenstein and Michael Sipser, GO is polynomial Space Hard, Journal of the Association for Computing Machinery, April 1980. [1] [2]