Y a-t-il une réduction des jeux de «porte et plaque de pression» qui n'explose pas la longueur de la solution?

12

Cet article prouve que dans un jeu avec des portes et des plaques de pression, il est difficile pour PSPACE de déterminer si l'avatar (du joueur) peut atteindre un emplacement donné. Cela est prouvé par une réduction de TQBF , et la longueur des solutions résultantes dépend exponentiellement du nombre de quantificateurs universels dans la formule.

Y a-t-il une réduction d'une machine NPSPACE à un tel jeu pour lequel la longueur des solutions du jeu est polynomialement liée à la longueur des chemins d'acceptation de la machine?

Jeffε
la source
1
brève esquisse d'un défn plus formel de "jeu avec portes et plaques de pression" [hélas, pas vraiment donné dans le journal en un seul endroit]. le jeu généralisé est une carte 2D infinie qui peut être représentée sous forme de graphique (de taille arbitraire) des espaces / régions de connexion. les nœuds du graphique sont des espaces / régions (équiv, cellules / tunnels, etc.), les bords sont des portes entre eux. les plaques de pression sont des interrupteurs contenus dans les espaces. un interrupteur commande l'ouverture d'une porte. les portes commencent dans un état arbitraire, peut-être certaines ouvertes, d'autres fermées. (etc.) ... cependant, il semble que l'auteur ne considère que les graphiques planaires.
vzn
en outre, la question semble être proche, ou presque équivalente, de la question de savoir si la longueur du chemin minimal d'une solution (comptée en arêtes) à travers le graphique est liée de manière polynomiale ou exponentielle à la taille du graphique / commutateurs. .. cela à son tour semble être étroitement lié à la question de savoir combien de cycles dans le chemin sont nécessaires ou s'ils ne le sont pas ...
vzn

Réponses:

2

Vous pouvez peut-être facilement simuler un LBA; l'idée est la suivante:

  • pour chaque cellule de la bande LBA, ajoutez un gadget de cellule qui ne peut être saisi que par le bas et sorti uniquement par le haut;Gi

  • le gadget possède une porte d'entrée qui simule la position de la tête (un seul est ouvert à chaque pas);C iCiCi

  • alors il y a deux portes de bits et ; est ouvert si la cellule contient un zéro, est ouvert s'il y a une cellule;O i Z i O iZiOiZiOi

  • les deux portes de mors mènent à une structure de contrôle similaire qui est faite par plusieurs couloirs à sens unique ; un couloir correspond à un état du LBA, et la porte du ème couloir est ouverte si et seulement si l'état actuel du LBA est ; i q iqiiqi

  • selon la table de transition (éventuellement non déterministe) du LBA, une traversée du couloir (ouvert) modifie l'état actuel du LBA et la configuration des portes de bits, ferme la porte et ouvre ou .C i + 1 C i - 1CiCi+1Ci1

Un gadget de cellule est esquissé dans la figure ci-dessous.

entrez la description de l'image ici

Des choix non déterministes peuvent être réalisés en divisant les couloirs des structures de contrôle en deux sous-couloirs ou plus, comme illustré dans la figure ci-dessous.

entrez la description de l'image ici

Remarque: si une plaque ne peut ouvrir / fermer qu'une seule porte, vous pouvez ajouter une structure auxiliaire avec des couloirs unidirectionnels (longs) qui (dés) activent les portes d'état distinctes de chaque cellule.

Marzio De Biasi
la source
Si une porte ne peut être ouverte que par une seule plaque et ne peut être fermée que par une seule plaque, vous pouvez utiliser des gadgets de croisement (que je pourrais décrire) pour laisser les couloirs ne conduire qu'à l'entrée de la cellule souhaitée (ce qui supprime la besoin des portes C1), mettre en œuvre Z1 et O1 avec beaucoup de portes différentes, chacune ayant une plaque de fermeture immédiatement après, et mettre en œuvre les portes q0, ..., q4 comme de nombreux mini-couloirs avec deux portes chacune suivies par une plaque qui ferme l'une de ces deux portes et une plaque qui ferme l'une des paires de portes ouvertes sur le qi de l'autre [valeur de cellule].
Indépendamment des suggestions de mon commentaire précédent, si le LBA n'est pas déterministe, alors les couloirs unidirectionnels auraient besoin de sous-couloirs, pour indiquer le choix non déterministe.
?? n'est pas la reconnaissance LBA = (N) PSPACE? semble qu'il serait plus utile si la réponse était formulée en termes de classe de complexité.
vzn
@RickyDemer: ok, j'ai ajouté un exemple de choix non déterministe. Utilisez-vous les métathéorèmes de Viglietta pour prouver la complexité de certains jeux?
Marzio De Biasi
Je lisais ses métathéorèmes et j'ai réalisé que c'est une chose à laquelle ils ne s'attaquent pas.
2

Un autre moyen rapide de prouver le Metatheorem 2c (dureté PSPACE lorsque les portes sont contrôlées par deux plaques) est d'utiliser le cadre logique de contrainte non déterministe ( RA Hearn et ED Demaine, Le modèle logique de calcul de contrainte non déterministe: réductions et applications ).

Dans ce cas, il suffit d'utiliser une série horizontale de paires de couloirs verticaux. L'état de chaque paire de couloirs représente la direction (vers l'intérieur / vers l'extérieur) d'une arête dans le graphique de contraintes d'origine. Il suffit de simuler le gadget AND et le gadget OR, comme illustré dans la figure ci-dessous.

entrez la description de l'image ici

Marzio De Biasi
la source
-5

ce type de recherche sur le lien entre les jeux vidéo et la complexité de calcul est assez intrigant mais il est également assez récent, généralement vieux de moins d'une décennie. Je soutiendrai ici qu'il y a parfois une subtilité qui manque parfois dans les analyses actuelles [je n'ai pas vu / remarqué cela souligné dans l'article cité ou dans d'autres articles jusqu'à présent] et qui empêche de répondre définitivement à la question posée.

pour prouver une relation avec un système de calcul, il faut être capable de mapper le système de calcul sur le jeu et vice versa. par exemple, dans l'article cité ci-dessus par Viglietta, il existe un concept selon lequel les plaques de pression et les portes (c'est-à-dire les portes de commande des plaques de pression) peuvent être "similaires" aux QBF. cette analogie est certainement viable car ils l'ont tracée. on peut utiliser un QBF pour résoudre un jeu avec des plaques de pression et des portes.

cependant, voici la subtilité. dans un jeu donné, les dispositions du jeu sont fondamentalement fixes. dans la conception de jeux vidéo, le concept de différentes mises en page est appelé "conception de mises en page" et n'est pas une "donnée" de tous les jeux. Par exemple, dans le jeu révolutionnaire Doom, les outils de conception de niveaux étaient open source, c'est-à-dire mis à la disposition des joueurs. en d'autres termes, la conception de niveaux arbitraires peut être considérée comme faisant partie du jeu. mais dans d'autres jeux considérés dans les journaux, les jeux vidéo tels que construits à l'origine ont des niveaux fixes. les documents n'en tiennent parfois pas explicitement compte.

par conséquent, il y a un argument solide à faire valoir que dans la plupart des jeux sans conception de niveaux ou dispositions aléatoires, les niveaux sont fixes, ce qui a un impact important sur la complexité réelle de la résolution du "jeu". c'est-à-dire, qu'est-ce que le "jeu" exactement? comprend-il des dispositions aléatoires et / ou une possibilité de conception de niveau? la conception de niveaux fait-elle partie de la cartographie informatique? ces questions sont passées sous silence dans les articles actuels.

Poussé à l'extrême opposé des articles, on pourrait dire que toutes les implémentations de jeux vidéo réels sont résolubles par les FSM car ils ont une mémoire finie !

pour qu'il y ait de vrais mappages de calcul, il faut essentiellement généraliser le jeu pour impliquer

  • niveaux avec une taille arbitraire! afin que cela puisse être mappé sur des MT avec des bandes "d'entrée" de taille arbitraire / illimitée.
  • conception de niveaux qui permet la création de ces niveaux.

un problème de mappage légèrement similaire se pose dans la recherche CA / Cellular Automata où il existe des idées sur l'utilisation de motifs périodiques infinis sur les CA comme "motifs de départ" pour prouver l'équivalence / l'exhaustivité de la MT.

Donc, en général, votre question n'est pas strictement définie tant que vous ne clarifiez pas mieux (c.-à-d . définissez de façon plus formelle / mathématique ) ce que vous entendez par "dans un jeu avec des portes et des plaques de pression" et d'une manière que même le papier ne définit pas apparemment strictement, en particulier écrit des idées sur la conception de niveaux, des niveaux de taille illimités, etc. mais avis que les « jeux » définis avec ces caractéristiques puis ont été abstraire loin des jeux vidéo réelle / réelle d'une manière très significative.

Donc, en bref, je pense que cette recherche est intéressante / utile, même si elle débute comme quelque peu informelle, et mérite des progrès supplémentaires, mais dans une certaine mesure, sa formalisation doit être rendue plus stricte, en particulier dans les définitions de base, si elle veut progresser davantage. il doit faire une distinction plus stricte / formelle / transparente entre les implémentations et les abstractions .

vzn
la source
par exemple, voici un article sur Battleship en tant que NP complet, mais il indique / décrit formellement mieux la généralisation NP complète du jeu de taille limitée. Les cuirassés comme problème de décision par Sevenster, sec2.
vzn
un autre exemple de subtilités dans la généralisation / l'abstraction du problème, la généralisation de la géométrie à 15 puzzles peut affecter son exhaustivité NP . notez qu'une grille carrée vs rectangulaire peut affecter les résultats.
vzn
7
Bien que ce soit un problème, je pense que votre affirmation selon laquelle cela est passé sous silence dans la littérature est surestimée. Et compte tenu de l'existence d'articles comme Fraenkel et al FOCS 1978 sur la complexité des contrôleurs, Even et Tarjan JACM 1976 sur Hex, et Robertson et Munro Util. Math. 1978 sur Instant Insanity, votre affirmation selon laquelle il s'agit d'un tout nouveau domaine est également très surestimée.
David Eppstein
évidemment les jeux en général étudiés à partir d'une vue TCS ne sont pas nouveaux, ses jeux vidéo qui le sont, comme le texte prend soin de le dire.
vzn
1
Mahjong solitaire : 1994. Démineur : 2000. Tetris : 2002. Ne sont-ils pas considérés comme des jeux vidéo, ou utilisez-vous une longue décennie ?
Peter Shor