Modèles de calcul, TD numéro 7

Natacha Portier vendredi 17 mars 2000

Un jeu est défini de la manière suivante. Le plateau de jeu est un ensemble discret de taille fini. Chaque élément du plateau a des voisins, un état, et les états sont en nombre fini. Par conséquent, le nombre de configurations possibles du plateau est fini. Les règles du jeu sont les manières valides de passer d’une configuration à l’autre. Certaines configurations sont gagnantes, et d’autres sont perdantes.

Les joueurs sont deux. Nous les appellerons Héloïse et Brian . Ils jouent chacun leur tour. Une partie est constituée d’une liste de configurations du plateau, la première étant la configuration initiale, et la dernière étant perdante ou gagnante.

Héloïse a une stratégie gagnante pour une certaine configuration initiale si elle peut gagner quelle que soit la façon dont joue Brian .

Le JEU est alors l’ensemble des configurations initiales pour lesquelles il existe une stratégie gagnante.

Question 1

Exprimer QBF comme un jeu.

Question 2 : Le jeu de la géographie

Héloïse choisit une ville, par exemple Lyon. Comme cette ville finit par N, Brian doit répondre par une ville qui commence par N, par exemple Nice. Brian peut alors répondre Edinbourgh. Une ville ne peut être citée qu’une fois, et le joueur qui ne peut plus citer de ville a perdu.

Question 2,1

Définir le plateau de jeu, les états, les règles, la configuration initiale et les configurations perdantes.

Tout graphe orienté fini peut-il être interprété de cette manière? (On ne s’encombrera pas du fait que l’alphabet latin n’a que 26 lettres...)

Question 2,2 Le problème GEO est défini comme l’ensemble des (G, s) où G est un graphe orienté fini quelconque, s un sommet de G et il existe une stratégie gagnante de départ s.

Donner un exemple dans GEO et un exemple hors GEO.

Question 2,3

Considérons un jeu qui satisfasse les deux conditions suivantes :

(a) La longueur d’une partie est bornée polynomialement en la taille de l’entrée.

(b) Etant donnée une configuration du plateau, il existe un algorithme ESPACE-P qui construit toutes les configurations suivantes possibles ou le cas échéant dit si la configuration est perdante ou gagnante. Plus précisément, il y a au plus un nombre exponentiel de configurations suivantes, et l’algorithme produit en espace polynomial chacune d’entre elle (par exemple, elles sont numérotées et on fournit à l’algorithme le numéro de la configuration désirée).

Montrez que GEO et QFB satisfont ces deux conditions.

Question 2,4

Montrer que tout JEU qui satisfait ces deux conditions est ESPACE-P.

Question 2,5

Réduire QBF à GEO et en déduire que GEO est ESPACE-P-complet.