En teoría de la complejidad computacional , un gadget es una subunidad de una instancia de problema que simula el comportamiento de una de las unidades fundamentales de un problema computacional diferente. Los gadgets se utilizan normalmente para construir reducciones de un problema computacional a otro, como parte de pruebas de completitud NP u otros tipos de dureza computacional. La técnica de diseño de componentes es un método para construir reducciones mediante el uso de dispositivos. [1]
Szabó (2009) remonta el uso de dispositivos a un artículo de 1954 sobre teoría de grafos de WT Tutte , en el que Tutte proporcionó dispositivos para reducir el problema de encontrar un subgrafo con restricciones de grado dadas a un problema de coincidencia perfecta . Sin embargo, la terminología de "dispositivo" tiene un origen posterior y no aparece en el artículo de Tutte. [2] [3]
Muchas pruebas de completitud NP se basan en reducciones de muchos uno de la satisfacibilidad 3 , el problema de encontrar una asignación satisfactoria a una fórmula booleana que es una conjunción (booleana y) de cláusulas, siendo cada cláusula la disyunción (booleana o) de tres términos, siendo cada término una variable booleana o su negación. Una reducción de este problema a un problema difícil sobre gráficos no dirigidos , como el problema del ciclo hamiltoniano o la coloración de gráficos , normalmente se basaría en dispositivos en forma de subgrafos que simulan el comportamiento de las variables y cláusulas de una instancia dada de 3 satisfacibilidad. . Estos elementos luego se pegarían entre sí para formar un único gráfico, un ejemplo difícil del problema de gráficos en cuestión. [4]
Por ejemplo, el problema de probar la colorabilidad 3 de gráficos puede demostrarse como NP completo mediante una reducción de la satisfacibilidad 3 de este tipo. La reducción utiliza dos vértices de gráfico especiales, etiquetados como "Tierra" y "Falso", que no forman parte de ningún gadget. Como se muestra en la figura, el dispositivo para una variable x consta de dos vértices conectados en un triángulo con el vértice del suelo; uno de los dos vértices del gadget está etiquetado con x y el otro está etiquetado con la negación de x . El artilugio de una cláusula ( t 0 ∨ t 1 ∨ t 2 ) consta de seis vértices, conectados entre sí, a los vértices que representan los términos t 0 , t 1 y t 2 , y a los vértices básicos y falsos por el bordes mostrados. Cualquier fórmula 3-CNF se puede convertir en un gráfico construyendo un dispositivo separado para cada una de sus variables y cláusulas y conectándolos como se muestra. [5]
En cualquier coloración triple del gráfico resultante, se pueden designar los tres colores como verdadero, falso o básico, donde falso y básico son los colores dados a los vértices falso y básico (necesariamente diferentes, ya que estos vértices se vuelven adyacentes por la construcción) y verdadero es el color restante no utilizado por ninguno de estos vértices. Dentro de un gadget de variable, sólo son posibles dos colores: el vértice etiquetado con la variable debe tener el color verdadero o falso, y el vértice etiquetado con la negación de la variable debe tener el color correspondiente falso o verdadero. De esta manera, las asignaciones válidas de colores a los dispositivos variables se corresponden uno a uno con las asignaciones de verdad a las variables: el comportamiento del dispositivo con respecto a la coloración simula el comportamiento de una variable con respecto a la asignación de verdad. Cada asignación de cláusula tiene una coloración válida de 3 colores si al menos uno de sus vértices de términos adyacentes está coloreado como verdadero, y no puede tener 3 colores si todos sus vértices de términos adyacentes están coloreados como falso. De esta manera, el gadget de cláusula puede colorearse si y sólo si la asignación de verdad correspondiente satisface la cláusula, por lo que nuevamente el comportamiento del gadget simula el comportamiento de una cláusula.
Agrawal et al. (1997) consideraron lo que llamaron "una forma radicalmente simple de reducción de dispositivos", en la que cada bit que describe parte de un dispositivo puede depender sólo de un número limitado de bits de la entrada, y utilizaron estas reducciones para demostrar un análogo de la reducción de Berman. –Conjetura de Hartmanis que establece que todos los conjuntos NP-completos son isomórficos en tiempo polinómico. [6]
La definición estándar de completitud NP implica reducciones de muchos uno en tiempo polinomial : un problema en NP es, por definición, NP-completo si todos los demás problemas en NP tienen una reducción de este tipo, y la forma estándar de demostrar que un problema en NP es NP-completo es encontrar una reducción de muchos-uno en tiempo polinómico a partir de un problema NP-completo conocido. Pero (en lo que Agrawal et al. llamaron "un hecho curioso, observado a menudo") todos los conjuntos que se sabía que eran NP-completos en ese momento podrían demostrarse completos utilizando la noción más fuerte de reducciones muchos uno de AC : es decir, reducciones que se puede calcular mediante circuitos de tamaño polinomial, profundidad constante y abanico ilimitado. Agrawal et al. demostró que todo conjunto que es NP-completo bajo reducciones AC 0 está completo bajo un tipo de reducción aún más restringido, NC reducciones muchos uno, utilizando circuitos de tamaño polinomial, profundidad constante y abanico de entrada acotado. En una reducción NC 0 , cada bit de salida de la reducción puede depender sólo de un número constante de bits de entrada. [6]
La conjetura de Berman-Hartmanis es un problema no resuelto en la teoría de la complejidad computacional que afirma que todas las clases de problemas NP-completos son isomórficos en tiempo polinómico. Es decir, si A y B son dos clases de problemas NP-completos, hay una reducción uno a uno en tiempo polinomial de A a B cuya inversa también es computable en tiempo polinomial. Agrawal et al. usó su equivalencia entre reducciones AC 0 y reducciones NC 0 para mostrar que todos los conjuntos completos para NP bajo reducciones AC 0 son AC 0 -isomorfos. [6]
Una aplicación de los dispositivos es demostrar la dureza de los resultados de aproximación, reduciendo un problema que se sabe que es difícil de aproximar a otro problema cuya dureza se va a probar. En esta aplicación, normalmente se tiene una familia de instancias del primer problema en las que hay una brecha en los valores de la función objetivo y en la que es difícil determinar si una instancia dada tiene una función objetivo que está en el lado bajo o en el lado bajo. en el lado alto de la brecha. Las reducciones utilizadas en estas pruebas, y los artilugios utilizados en las reducciones, deben preservar la existencia de esta brecha, y la fuerza del resultado de inaproximabilidad derivado de la reducción dependerá de qué tan bien se preserve la brecha.
Trevisan et al. (2000) formalizan el problema de encontrar dispositivos que preserven las brechas, para familias de problemas de satisfacción de restricciones en las que el objetivo es maximizar el número de restricciones satisfechas. [7] Dan como ejemplo una reducción de 3-satisfacibilidad a 2-satisfacibilidad realizada por Garey, Johnson y Stockmeyer (1976), en la que el dispositivo que representa una cláusula 3-SAT consta de diez cláusulas 2-SAT, y en el que una La asignación de verdad que satisface la cláusula 3-SAT también satisface al menos siete cláusulas del dispositivo, mientras que una asignación de verdad que no cumple una cláusula 3-SAT tampoco satisface más de seis cláusulas del dispositivo. [8] Utilizando este dispositivo, y el hecho de que (a menos que P = NP ) no exista un esquema de aproximación en tiempo polinómico para maximizar el número de cláusulas 3-SAT que satisface una asignación de verdad, se puede demostrar que tampoco existe una aproximación. esquema para MAX 2-SAT.
Trevisan et al. muestran que, en muchos casos de los problemas de satisfacción de restricciones que estudian, los dispositivos que conducen a los resultados de inaproximabilidad más fuertes posibles pueden construirse automáticamente, como solución a un problema de programación lineal . Las mismas reducciones basadas en dispositivos también se pueden utilizar en la otra dirección, para transferir algoritmos de aproximación de problemas más fáciles a problemas más difíciles. Por ejemplo, Trevisan et al. proporcionar un dispositivo óptimo para reducir 3-SAT a una variante ponderada de 2-SAT (que consta de siete cláusulas 2-SAT ponderadas) que es más fuerte que la de Garey, Johnson y Stockmeyer (1976); usándolo, junto con algoritmos de aproximación de programación semidefinida conocidos para MAX 2-SAT, proporcionan un algoritmo de aproximación para MAX 3-SAT con una relación de aproximación de 0,801, mejor que los algoritmos conocidos anteriormente.