Lógica de restricciones no deterministas

En informática teórica , la lógica de restricciones no determinista es un sistema combinatorio en el que se asigna una orientación a las aristas de un grafo no dirigido ponderado , sujeta a ciertas restricciones. Esta orientación puede modificarse mediante pasos en los que se invierte una sola arista, sujeta a las mismas restricciones. Se trata de una forma de lógica reversible, ya que cada secuencia de cambios de orientación de las aristas puede deshacerse.

Se ha demostrado que los problemas de reconfiguración para la lógica de restricciones, que requieren una secuencia de movimientos para conectar ciertos estados, conectar todos los estados o invertir una arista específica, son PSPACE-completos . Estos resultados de dificultad constituyen la base para demostrar que diversos juegos y rompecabezas son PSPACE-difíciles o PSPACE-completos.

En la versión más simple de la lógica de restricciones no deterministas, cada arista de un grafo no dirigido tiene un peso de uno o dos. (Los pesos también se pueden representar gráficamente dibujando las aristas de peso uno en rojo y las de peso dos en azul). Se requiere que el grafo sea cúbico : cada vértice es incidente a tres aristas y, además, cada vértice debe ser incidente a un número par de aristas rojas. ^{[ 2 ]}

Se requiere que las aristas estén orientadas de tal manera que al menos dos unidades de peso se orienten hacia cada vértice: debe haber al menos una arista azul entrante o al menos dos aristas rojas entrantes. La orientación puede cambiar mediante pasos en los que se invierte una sola arista, respetando estas restricciones. ^{[ 2 ]}

Las formas más generales de lógica de restricciones no deterministas permiten una mayor variedad de pesos de aristas, más aristas por vértice y diferentes umbrales para la cantidad de peso entrante que debe tener cada vértice. Un grafo con un sistema de pesos de aristas y umbrales de vértices se denomina grafo de restricciones . El caso restringido en el que los pesos de las aristas son todos uno o dos, los vértices requieren dos unidades de peso entrante y todos los vértices tienen tres aristas incidentes con un número par de aristas rojas, se denomina grafo de restricciones y/o . ^{[ 2 ]}

La razón del nombre de los grafos de restricciones AND/OR es que los dos tipos posibles de vértices en un grafo de restricciones AND/OR se comportan de manera similar a una puerta AND y una puerta OR en lógica booleana . Un vértice con dos aristas rojas y una azul se comporta como una puerta AND, ya que requiere que ambas aristas rojas apunten hacia adentro antes de que la arista azul pueda apuntar hacia afuera. Un vértice con tres aristas azules se comporta como una puerta OR, con dos de sus aristas designadas como entradas y la tercera como salida, ya que requiere que al menos una arista de entrada apunte hacia adentro antes de que la arista de salida pueda apuntar hacia afuera. ^{[ 2 ]}

Por lo general, los problemas de lógica de restricciones se definen en torno a la búsqueda de configuraciones válidas de grafos de restricciones. Los grafos de restricciones son grafos no dirigidos con dos tipos de aristas:

• bordes rojos con peso${\displaystyle 1}$
• bordes azules con peso${\displaystyle 2}$

Utilizamos grafos de restricciones como modelos de computación, donde consideramos el grafo completo como una máquina. Una configuración de la máquina consiste en el grafo junto con una orientación específica de sus aristas. Llamamos válida a una configuración si satisface la restricción de entrada: cada vértice debe tener un peso de entrada de al menos${\displaystyle 2}$. En otras palabras, la suma de los pesos de las aristas que entran en un vértice dado debe ser al menos${\displaystyle 2}$más que la suma de los pesos de las aristas que salen del vértice.

También definimos un movimiento en un grafo de restricciones como la acción de invertir la orientación de una arista, de manera que la configuración resultante siga siendo válida.

Supongamos que se nos da un grafo de restricciones, una configuración inicial y una configuración final. Este problema pregunta si existe una secuencia de movimientos válidos que lo lleven de la configuración inicial a la configuración final. Este problema es PSPACE-Completo para grafos 3-regulares o de grado máximo 3. ^{[ 3 ]} La reducción se deriva de QSAT y se describe a continuación.

Los siguientes problemas, sobre grafos de restricciones y/o sus orientaciones, son PSPACE-completos: ^{[ 2 ]}

• Dada una orientación y un borde especificado e , se comprueba si existe una secuencia de pasos desde la orientación dada que eventualmente invierta el borde e . 
• Probar si una orientación puede cambiarse a otra mediante una secuencia de pasos.
• Dados dos bordes e y f con direcciones específicas, se comprueba si existen dos orientaciones para todo el grafo, una con la dirección especificada en e y la otra con la dirección especificada en f , que puedan transformarse una en la otra mediante una secuencia de pasos.

La prueba de que estos problemas son difíciles implica una reducción a partir de fórmulas booleanas cuantificadas , basada en la interpretación lógica de grafos de restricciones AND/OR. Requiere dispositivos adicionales para simular cuantificadores y para convertir señales transportadas por aristas rojas en señales transportadas por aristas azules (o viceversa), lo cual se puede lograr mediante combinaciones de vértices AND y vértices OR. ^{[ 2 ]}

Estos problemas siguen siendo PSPACE-completos incluso para grafos de restricciones que forman grafos planares . La prueba de esto implica la construcción de dispositivos de cruce que permiten que dos señales independientes se crucen. También es posible imponer una restricción adicional, preservando la dificultad de estos problemas: se puede exigir que cada vértice con tres aristas azules forme parte de un triángulo con una arista roja. Dicho vértice se denomina protegido o , y tiene la propiedad de que (en cualquier orientación válida de todo el grafo) no es posible que ambas aristas azules del triángulo estén dirigidas hacia adentro. Esta restricción facilita la simulación de estos vértices en reducciones de dificultad para otros problemas. ^{[ 2 ]} Además, se puede exigir que los grafos de restricciones tengan un ancho de banda limitado , y los problemas sobre ellos seguirán siendo PSPACE-completos. ^{[ 4 ]}

La reducción se deriva de QSAT. Para incorporar una fórmula QSAT, necesitamos crear los gadgets AND, OR, NOT, UNIVERSAL, EXISTENTIAL y Converter (para cambiar el color) en el grafo de restricciones. La idea es la siguiente:

• Un vértice AND es un vértice que tiene dos aristas rojas incidentes (entradas) y una arista azul incidente (salida).
• Un vértice OR es un vértice que tiene tres aristas azules incidentes (dos de entrada y una de salida).

Los demás dispositivos también pueden crearse de esta manera. La construcción completa está disponible en el sitio web de Erik Demaine . ^{[ 5 ]} La construcción completa también se explica de forma interactiva. ^{[ 6 ]}

Las aplicaciones originales de la lógica de restricciones no deterministas la utilizaron para demostrar la completitud PSPACE de rompecabezas de bloques deslizantes como Rush Hour y Sokoban . Para ello, basta con mostrar cómo simular aristas y orientaciones de aristas, vértices y vértices protegidos en estos rompecabezas. ^{[ 2 ]}

La lógica de restricciones no deterministas también se ha utilizado para demostrar la dificultad de las versiones de reconfiguración de problemas clásicos de optimización de grafos, incluidos el conjunto independiente , la cobertura de vértices y el conjunto dominante , en grafos planares de ancho de banda limitado. En estos problemas, se debe cambiar una solución al problema dado por otra, moviendo un vértice a la vez dentro o fuera del conjunto de soluciones , manteniendo la propiedad de que en todo momento los vértices restantes formen una solución. ^{[ 4 ]}