Lógica de restricción no determinista
En informática teórica , la lógica de restricción no determinista es un sistema combinatorio en el que se da una orientación a los bordes de un gráfico no dirigido ponderado , sujeto a ciertas restricciones. Se puede cambiar esta orientación por pasos en los que se invierte un solo borde, sujeto a las mismas restricciones. Se ha demostrado que el problema de lógica de restricción y sus variantes son PSPACE-completo para determinar si existe una secuencia de movimientos que invierte un borde específico y son muy útiles para mostrar varios juegos y rompecabezas que son PSPACE-difícil o PSPACE-completo.
Esta es una forma de lógica reversible en la que cada secuencia de cambios de orientación de los bordes se puede deshacer. La dureza de este problema se ha utilizado para demostrar que muchos juegos y rompecabezas tienen una gran complejidad de juego .
En la versión más simple de la lógica de restricción no determinista, cada borde de un gráfico no dirigido tiene un peso de uno o dos. (Los pesos también se pueden representar gráficamente dibujando los bordes del peso uno en rojo y los bordes del peso dos en azul ) . a un número par de bordes rojos. [2]
Los bordes deben estar orientados de tal manera que al menos dos unidades de peso estén orientadas hacia cada vértice: debe haber al menos un borde azul entrante o al menos dos bordes rojos entrantes. Una orientación puede cambiar por pasos en los que se invierte un solo borde, respetando estas restricciones. [2]
Las formas más generales de lógica de restricción no determinista permiten una mayor variedad de pesos de borde, más bordes por vértice y diferentes umbrales para la cantidad de peso entrante que debe tener cada vértice. Un gráfico con un sistema de pesos de borde y umbrales de vértice se denomina gráfico de restricción . 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 y/o gráficos de restricción . [2]
El motivo del nombre y/o gráficos de restricciones es que los dos posibles tipos de vértices en un gráfico de restricciones y/o se comportan de alguna manera como una puerta AND y una puerta OR en lógica booleana . Un vértice con dos bordes rojos y un borde azul se comporta como una puerta AND en el sentido de que requiere que ambos bordes rojos apunten hacia adentro antes de que el borde azul apunte hacia afuera. Un vértice con tres bordes azules se comporta como una puerta OR, con dos de sus bordes designados como entradas y el tercero como salida, ya que requiere que al menos un borde de entrada apunte hacia adentro antes de que el borde de salida apunte hacia afuera. [2]
