En la teoría de la complejidad computacional , la geografía generalizada es un problema PSPACE-completo bien conocido .
La geografía es un juego infantil en el que los jugadores se turnan para nombrar ciudades de cualquier parte del mundo. Cada ciudad elegida debe comenzar con la misma letra que terminaba el nombre de la ciudad anterior. No se permite la repetición. El juego comienza con una ciudad inicial arbitraria y termina cuando un jugador pierde porque no puede continuar.
Para visualizar el juego, se puede construir un grafo dirigido cuyos nodos sean cada una de las ciudades del mundo. Se añade una flecha desde el nodo N 1 al nodo N 2 si y solo si la ciudad que etiqueta N 2 comienza con la letra que termina el nombre de la ciudad que etiqueta el nodo N 1 . En otras palabras, dibujamos una flecha de una ciudad a otra si la primera puede llevar a la segunda de acuerdo con las reglas del juego. Cada arista alterna en el grafo dirigido corresponde a cada jugador (para un juego de dos jugadores). El primer jugador que no pueda extender la ruta pierde. En la figura siguiente se muestra una ilustración del juego (que contiene algunas ciudades de Michigan).
En un juego de geografía generalizada (GG), reemplazamos el gráfico de los nombres de las ciudades con un gráfico dirigido arbitrario. El siguiente gráfico es un ejemplo de un juego de geografía generalizada.
Definimos P 1 como el jugador que mueve primero y P 2 como el jugador que mueve segundo y nombramos los nodos N 1 a N n . En la figura anterior, P 1 tiene una estrategia ganadora de la siguiente manera: N 1 apunta solo a los nodos N 2 y N 3 . Por lo tanto, el primer movimiento de P 1 debe ser una de estas dos opciones. P 1 elige N 2 (si P 1 elige N 3 , entonces P 2 elegirá N 9 ya que es la única opción y P 1 perderá). A continuación, P 2 elige N 4 porque es la única opción restante. P 1 ahora elige N 5 y P 2 posteriormente elige N 3 o N 7 . Independientemente de la elección de P 2 , P 1 elige N 9 y P 2 no tiene opciones restantes y pierde el juego.
El problema de determinar qué jugador tiene una estrategia ganadora en un juego de geografía generalizada es PSPACE-completo .
Sea GG = { ⟨ G , b ⟩ | P 1 tiene una estrategia ganadora para el juego de geografía generalizada jugado en el grafo G comenzando en el nodo b }; para demostrar que GG ∈ PSPACE , presentamos un algoritmo recursivo en el espacio polinomial que determina qué jugador tiene una estrategia ganadora. Dada una instancia de GG, ⟨ G , n start ⟩ donde G es un grafo dirigido y n start es el nodo de inicio designado, el algoritmo M procede de la siguiente manera:
En M (⟨ G , n inicio ⟩):
El algoritmo M claramente decide GG. Está en PSPACE porque el único espacio de trabajo polinomial no obvio consumido está en la pila de recursión. El espacio consumido por la pila de recursión es polinomial porque cada nivel de recursión agrega un solo nodo a la pila, y hay como máximo n niveles, donde n es el número de nodos en G. Esto es esencialmente equivalente a una búsqueda en profundidad .
La siguiente prueba se debe a David Lichtenstein y Michael Sipser. [1]
Para establecer la PSPACE-dureza de GG, podemos reducir el problema FORMULA-GAME (que se sabe que es PSPACE-duro ) a GG en tiempo polinomial ( P ). En resumen, una instancia del problema FORMULA-GAME consiste en una fórmula booleana cuantificada φ = ∃ x 1 ∀ x 2 ∃ x 3 ... Qx k (ψ) donde Q es ∃ o ∀. El juego lo juegan dos jugadores, P a y P e , que se alternan eligiendo valores para x i sucesivos . P e gana el juego si la fórmula ψ termina siendo verdadera , y P a gana si ψ termina siendo falsa . Se supone que la fórmula ψ está en forma normal conjuntiva .
En esta prueba, asumimos que la lista de cuantificadores comienza y termina con el calificador existencial ∃, para simplificar. Nótese que cualquier expresión puede convertirse a esta forma agregando variables ficticias que no aparecen en ψ.
Al construir un gráfico G como el que se muestra arriba, demostraremos que cualquier instancia de JUEGO DE FÓRMULAS puede reducirse a una instancia de Geografía Generalizada, donde la estrategia óptima para P 1 es equivalente a la de P e , y la estrategia óptima para P 2 es equivalente a la de P a .
La cadena vertical izquierda de nodos está diseñada para imitar el procedimiento de elección de valores para las variables en FORMULA-GAME. Cada estructura de diamante corresponde a una variable cuantificada. Los jugadores se turnan para decidir los caminos en cada nodo de ramificación. Debido a que asumimos que el primer cuantificador sería existencial, P 1 va primero, seleccionando el nodo izquierdo si x 1 es verdadero y el nodo derecho si x 1 es falso . Cada jugador debe tomar turnos forzados, y luego P 2 elige un valor para x 2 . Estas asignaciones alternas continúan hacia el lado izquierdo. Después de que ambos jugadores pasen por todos los diamantes, es nuevamente el turno de P 1 , porque asumimos que el último cuantificador es existencial. P 1 no tiene más opción que seguir el camino hacia el lado derecho del gráfico. Luego es el turno de P 2 para hacer un movimiento.
Cuando la jugada llega al lado derecho del gráfico, es similar al final de la jugada en el juego de fórmulas. Recordemos que en el juego de fórmulas, P e gana si ψ es verdadero , mientras que P a gana si ψ es falso . El lado derecho del gráfico garantiza que P 1 gane si y solo si P e gana, y que P 2 gane si y solo si P a gana.
Primero mostramos que P 2 siempre gana cuando P a gana. Si P a gana, ψ es falso . Si ψ es falso , existe una cláusula insatisfactoria. P 2 elegirá una cláusula insatisfactoria para ganar. Luego, cuando sea el turno de P 1 , debe elegir un literal en esa cláusula elegida por P 2. Dado que todos los literales en la cláusula son falsos , no se conectan a nodos visitados previamente en la cadena vertical izquierda. Esto permite a P 2 seguir la conexión al nodo correspondiente en un diamante de la cadena izquierda y seleccionarlo. Sin embargo, P 1 ahora no puede seleccionar ningún nodo adyacente y pierde.
Ahora demostramos que P 1 siempre gana cuando P e gana. Si P e gana, ψ es verdadero . Si ψ es verdadero , cada cláusula en el lado derecho del gráfico contiene un literal verdadero . P 2 puede elegir cualquier cláusula. Entonces P 1 elige el literal que es verdadero . Y como es verdadero , su nodo adyacente en el nodo vertical izquierdo ya ha sido seleccionado, por lo que P 2 no tiene movimientos que hacer y pierde.
La geografía generalizada es PSPACE-completa, incluso cuando se juega en grafos planares . La siguiente prueba es del teorema 3 de. [1]
Dado que GG planar es un caso especial de GG, y GG está en PSPACE, entonces GG planar está en PSPACE. Queda por demostrar que GG planar es PSPACE-hard. Esto se puede demostrar mostrando cómo convertir un grafo arbitrario en un grafo planar, de modo que un juego de GG jugado en este grafo tendrá el mismo resultado que en el grafo original.
Para ello, sólo es necesario eliminar todos los cruces de aristas del grafo original. Dibujamos el grafo de forma que no haya tres aristas que se intersequen en un punto y que no se puedan utilizar en el mismo juego pares de aristas que se crucen. Esto no es posible en general, pero siempre es posible para el grafo construido a partir de una instancia de FORMULA-GAME; por ejemplo, podríamos tener sólo las aristas de los vértices de la cláusula implicadas en los cruces. Ahora reemplazamos cada cruce con esta construcción:
El resultado es un gráfico plano, y el mismo jugador puede forzar una victoria como en el gráfico original: si un jugador elige moverse "hacia arriba" desde V en el juego transformado, entonces ambos jugadores deben continuar moviéndose "hacia arriba" hacia W o perderán inmediatamente. Por lo tanto, moverse "hacia arriba" desde V en el juego transformado simula el movimiento V→W en el juego original. Si V→W es un movimiento ganador, entonces moverse "hacia arriba" desde V en el juego transformado también es un movimiento ganador, y viceversa.
Por lo tanto, el juego de GG jugado en el gráfico transformado tendrá el mismo resultado que en el gráfico original. Esta transformación requiere un tiempo que es un múltiplo constante del número de intersecciones de aristas en el gráfico original, por lo que requiere un tiempo polinómico.
Por lo tanto, el GG planar es PSPACE-completo.
El GG jugado en gráficos bipartitos planares con grado máximo 3 sigue siendo PSPACE-completo, al reemplazar los vértices de grado mayor que 3 con una cadena de vértices con grado como máximo 3. La prueba está en [1] y utiliza la siguiente construcción:
Si un jugador utiliza cualquiera de las entradas a esta construcción, el otro jugador elige qué salida utilizará. Además, la construcción solo se puede recorrer una vez, porque siempre se visita el vértice central. Por lo tanto, esta construcción es equivalente al vértice original.
Una variante de GG se llama geografía de aristas , donde después de cada movimiento, se borra la arista por la que pasó el jugador. Esto contrasta con el GG original, donde después de cada movimiento, se borra el vértice en el que se encontraba el jugador. Desde este punto de vista, el GG original puede llamarse geografía de vértices .
La geografía de aristas es PSPACE-completa. Esto se puede demostrar utilizando la misma construcción que se utilizó para la geografía de vértices. [2]
También se puede considerar jugar cualquiera de los juegos de geografía en un gráfico no dirigido (es decir, las aristas se pueden recorrer en ambas direcciones). Fraenkel, Scheinerman y Ullman [3] muestran que la geografía de vértices no dirigida se puede resolver en tiempo polinomial, mientras que la geografía de aristas no dirigida es PSPACE-completa, incluso para gráficos planares con un grado máximo de 3. Si el gráfico es bipartito, entonces la geografía de aristas no dirigidas se puede resolver en tiempo polinomial.
Dado que GG es PSPACE-completo , no existe ningún algoritmo de tiempo polinomial para el juego óptimo en GG a menos que P = PSPACE . Sin embargo, puede que no sea tan fácil demostrar la complejidad de otros juegos porque ciertos juegos (como el ajedrez ) contienen un número finito de posiciones de juego, lo que hace difícil (o imposible) formular una aplicación a un problema PSPACE-completo . A pesar de esto, la complejidad de ciertos juegos aún se puede analizar por generalización (por ejemplo, a un tablero n × n ). Consulte las referencias para una prueba de Go generalizado , como corolario de la prueba de la completitud de GG.