¿Existe una reducción en los juegos de "puerta y placa de presión" que no explote la longitud de la solución?

12

Este documento demuestra que en un juego con puertas y placas de presión, es difícil para PSPACE determinar si el avatar (del jugador) puede o no alcanzar una ubicación determinada. Esto se demuestra mediante una reducción de TQBF , y la longitud de las soluciones resultantes depende exponencialmente del número de cuantificadores universales en la fórmula.

¿Existe una reducción de una máquina NPSPACE a un juego para el que la longitud de las soluciones del juego está polinomialmente relacionada con la longitud de las rutas de aceptación de la máquina?

Jeffε
fuente
1
breve bosquejo de una definición más formal de "juego con puertas y placas de presión" [por desgracia, no se da realmente en el periódico en un solo lugar]. El juego generalizado es un mapa 2D infinito que puede representarse como un gráfico (de tamaño arbitrario) de espacios / regiones de conexión. los nodos del gráfico son espacios / regiones (equiv, celdas / túneles, etc.), los bordes son puertas entre ellos. Las placas de presión son interruptores contenidos en los espacios. Un interruptor controla la apertura de la puerta. las puertas comienzan en un estado arbitrario, tal vez algunas abiertas, otras cerradas. (etc.) ... sin embargo, parece que el autor solo está considerando gráficos planos.
vzn
Además, la pregunta parece estar cerca, o casi equivalente, a la pregunta de si la longitud de la ruta mínima de una solución (contada en los bordes) a través del gráfico está polinomial o exponencialmente relacionada con el tamaño del gráfico / interruptores. .. esto a su vez parece estar estrechamente relacionado con la pregunta de cuántos ciclos en el camino son necesarios o si no lo son ...
vzn

Respuestas:

2

Quizás pueda simular fácilmente un LBA; La idea es la siguiente:

  • Gi

  • CiCi

  • ZiOiZiOi

  • qiiqi

  • CiCi+1Ci1

Un dispositivo celular se bosqueja en la figura a continuación.

ingrese la descripción de la imagen aquí

Se pueden realizar elecciones no deterministas dividiendo los corredores en las estructuras de control en dos o más subcorredores como se muestra en la figura a continuación.

ingrese la descripción de la imagen aquí

Nota: si una placa solo puede abrir / cerrar una sola puerta, entonces puede agregar una estructura auxiliar con corredores unidireccionales (largos) que (des) activen las puertas de estado distintas de cada celda.

Marzio De Biasi
fuente
Si una puerta solo se puede abrir con una sola placa y solo se puede cerrar con una sola placa, entonces puede usar dispositivos cruzados (que podría describir) para permitir que los corredores conduzcan solo a la entrada de la celda deseada (que elimina el necesidad de las puertas C1), implemente Z1 y O1 con muchas puertas diferentes, cada una de las cuales tiene una placa de cierre inmediatamente después, e implemente las puertas q0, ..., q4 como muchos mini-corredores con dos puertas cada una seguida por una placa que cierra una de esas dos puertas y una placa que cierra una de las puertas abiertas en el qi del otro [valor de celda].
Independientemente de las sugerencias en mi comentario anterior, si el LBA no es determinista, entonces los corredores unidireccionales necesitarían subcorredores, para indicar la elección no determinista.
?? ¿no es reconocimiento LBA = (N) PSPACE? Parece que sería más útil si la respuesta se formulara en términos de una clase de complejidad.
vzn
@RickyDemer: ok, agregué un ejemplo de una opción no determinista. ¿Estás utilizando los metateoremas de Viglietta para demostrar la complejidad de algunos juegos?
Marzio De Biasi
Estaba leyendo sus metateoremas, y me di cuenta de que esto es algo que no abordan.
2

Otra forma rápida de probar el Metatheorem 2c (dureza PSPACE cuando las puertas están controladas por dos placas) es usar el marco lógico de restricción no determinista ( RA Hearn y ED Demaine, el modelo lógico de restricción no computacional de cómputo: reducciones y aplicaciones ).

En este caso, es suficiente usar una serie horizontal de corredores-pares verticales. El estado de cada par de corredores representa la dirección (hacia adentro / hacia afuera) de un borde en el gráfico de restricción original. Es suficiente simular el gadget AND y el gadget OR, como se muestra en la figura a continuación.

ingrese la descripción de la imagen aquí

Marzio De Biasi
fuente
-5

Este tipo de investigación de relacionar los videojuegos con la complejidad computacional es bastante intrigante, pero también es bastante nuevo, generalmente tiene menos de una década. Argumentaré aquí que hay sutilezas que a veces se pasan por alto en los análisis actuales [no he visto / notado esto señalado en el documento citado u otros documentos hasta ahora] y eso impide responder definitivamente a la pregunta planteada.

Para probar una relación con un sistema computacional, uno debe ser capaz de mapear el sistema computacional en el juego y viceversa. Por ejemplo, en el artículo de Viglietta citado anteriormente, existe el concepto de que las placas de presión y las puertas (es decir, las puertas de control de las placas de presión) pueden ser "similares" a los QBF. Esta analogía es ciertamente viable ya que la han trazado. uno puede usar un QBF para resolver un juego con placas de presión y puertas.

Sin embargo, aquí está la sutileza. en un juego dado, los diseños del juego son básicamente fijos. En el diseño de videojuegos, el concepto de diferentes diseños se llama "diseño de diseño" y no es un "dado" de todos los juegos. Por ejemplo, en el innovador juego Doom, las herramientas de diseño de niveles fueron de código abierto, es decir, se pusieron a disposición de los jugadores para su uso. en otras palabras, el diseño de nivel arbitrario puede considerarse parte del juego. pero en otros juegos considerados en documentos, los videojuegos como se construyeron originalmente tienen niveles fijos. los documentos a veces no tienen esto explícitamente en cuenta.

por lo tanto, hay un fuerte argumento para argumentar que en la mayoría de los juegos sin diseño de niveles, o diseños aleatorios, los niveles son fijos, y esto tiene un gran impacto en la complejidad real de resolver el "juego". es decir, ¿qué es exactamente el "juego"? ¿incluye diseños aleatorios y / o posibilidad de diseño de nivel? ¿Es el diseño de nivel parte de la asignación computacional? estos temas se pasan por alto en algunos artículos actuales.

llevado al extremo opuesto de los documentos, se podría argumentar que todas las implementaciones de videojuegos reales son solucionables por FSM porque tienen memoria finita .

para que haya mapeos computacionales reales, básicamente uno debe generalizar el juego para involucrar

  • niveles con tamaño arbitrario! para que esto se pueda asignar a TM con cintas de "entrada" de tamaño arbitrario / ilimitado.
  • Diseño de nivel que permite la creación de estos niveles.

surge un problema de mapeo ligeramente similar en la investigación de CA / Autómatas Celulares donde hay ideas sobre el uso de patrones periódicos infinitos en las AC como "patrones iniciales" para probar la equivalencia / integridad de TM.

así que, en general, su pregunta no está estrictamente definida hasta que aclare mejor (es decir, defina más formal / matemáticamente ) lo que quiere decir con "en un juego con puertas y placas de presión" y de una manera que incluso el documento aparentemente no define estrictamente, especialmente Wrt a ideas sobre diseño de niveles, niveles de tamaño ilimitados, etc. pero aviso de que los "juegos" con estas características definidas a continuación, se han abstraído lejos de los juegos de vídeo real / real de una manera muy significativa.

en resumen, creo que esta es una investigación interesante / que vale la pena, aunque comienza como algo informal, y merece un mayor avance, pero hasta cierto punto su formalización debe hacerse más estrictamente especialmente en las definiciones básicas para avanzar más. debe hacer una distinción más estricta / formal / transparente entre las implementaciones y las abstracciones .

vzn
fuente
por ejemplo, aquí hay un documento sobre Battleship como NP completo, pero mejor / formalmente declara / describe la generalización completa de NP del juego de tamaño limitado. Los acorazados como un problema de decisión de Sevenster, sec2.
vzn
Otro ejemplo de sutilezas en la generalización / abstracción del problema, la generalización de la geometría de 15 rompecabezas puede afectar su integridad NP . tenga en cuenta que una cuadrícula cuadrada vs rectangular puede afectar los resultados
vzn
77
Si bien este es un problema, creo que su afirmación de que esto se pasa por alto en la literatura está exagerada. Y dada la existencia de artículos como Fraenkel et al FOCS 1978 sobre la complejidad de las fichas, Even y Tarjan JACM 1976 sobre Hex, y Robertson y Munro Util. Matemáticas. 1978 en Instant Insanity, su afirmación de que esta es un área completamente nueva también es exagerada.
David Eppstein
obviamente, los juegos en general estudiados desde una vista TCS no son nuevos, sus videojuegos sí lo son, como el texto es cuidadoso de decir.
vzn
1
Solitario Mahjong : 1994. Buscaminas : 2000. Tetris : 2002. ¿No cuentan como videojuegos, o usas una larga década ?
Peter Shor