En la 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 NP-completitud u otros tipos de dificultad computacional. La técnica de diseño de componentes es un método para construir reducciones mediante el uso de gadgets. [1]
Szabó (2009) rastrea el uso de gadgets a un artículo de 1954 sobre teoría de grafos escrito por WT Tutte , en el que Tutte proporcionó gadgets para reducir el problema de encontrar un subgrafo con restricciones de grado dadas a un problema de emparejamiento perfecto . Sin embargo, la terminología "gadget" tiene un origen posterior y no aparece en el artículo de Tutte. [2] [3]
Muchas pruebas de NP-completitud se basan en reducciones de muchos-uno a partir de la 3-satisfacibilidad , 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, y siendo cada término una variable booleana o su negación. Una reducción de este problema a un problema difícil sobre grafos no dirigidos , como el problema del ciclo hamiltoniano o la coloración de grafos , normalmente se basaría en artilugios en forma de subgrafos que simulan el comportamiento de las variables y cláusulas de una instancia dada de 3-satisfacibilidad. Estos artilugios se pegarían entonces para formar un único grafo, una instancia difícil para el problema de grafos en consideración. [4]
Por ejemplo, el problema de probar la 3-colorabilidad de los grafos puede demostrarse como NP-completo mediante una reducción de la 3-satisfacibilidad de este tipo. La reducción utiliza dos vértices de grafos especiales, etiquetados como "Fundamental" y "Falso", que no son parte de ningún dispositivo. 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 base; uno de los dos vértices del dispositivo está etiquetado con x y el otro está etiquetado con la negación de x . El dispositivo para 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 base y falso por las aristas que se muestran. Cualquier fórmula 3-CNF se puede convertir en un grafo construyendo un dispositivo separado para cada una de sus variables y cláusulas y conectándolos como se muestra. [5]
En cualquier coloración de 3 colores del gráfico resultante, se pueden designar los tres colores como verdadero, falso o fundamental, donde falso y fundamental son los colores dados a los vértices falso y fundamental (necesariamente diferentes, ya que estos vértices se hacen adyacentes por la construcción) y verdadero es el color restante no utilizado por ninguno de estos vértices. Dentro de un gadget variable, solo son posibles dos coloraciones: el vértice etiquetado con la variable debe colorearse como verdadero o falso, y el vértice etiquetado con la negación de la variable debe colorearse correspondientemente como falso o verdadero. De esta manera, las asignaciones válidas de colores a los gadgets variables corresponden uno a uno con las asignaciones de verdad a las variables: el comportamiento del gadget 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 de 3 colores válida si al menos uno de sus vértices de término adyacentes está coloreado como verdadero, y no puede ser de 3 colores si todos sus vértices de término adyacentes están coloreados como falso. De esta manera, el gadget de cláusula se puede colorear si y solo 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 gadgets", en la que cada bit que describe parte de un gadget puede depender solo de un número limitado de bits de la entrada, y usaron estas reducciones para demostrar un análogo de la conjetura de Berman-Hartmanis que afirma que todos los conjuntos NP-completos son isomorfos en tiempo polinomial. [6]
La definición estándar de NP-completitud implica reducciones de muchos-uno en tiempo polinómico : un problema en NP es por definición NP-completo si cada otro problema en NP tiene una reducción de este tipo para él, y la forma estándar de probar 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 para él. Pero (en lo que Agrawal et al. llamó "un hecho curioso, observado a menudo") todos los conjuntos que se sabía que eran NP-completos en ese momento podrían probarse completos usando la noción más fuerte de reducciones de muchos-uno AC : es decir, reducciones que pueden calcularse mediante circuitos de tamaño polinómico, profundidad constante y abanico de entrada ilimitado. Agrawal et al. probaron que cada conjunto que es NP-completo bajo reducciones AC 0 es completo bajo un tipo de reducción aún más restringido, reducciones de muchos-uno NC , usando circuitos de tamaño polinómico, profundidad constante y abanico de entrada acotado. En una reducción NC 0 , cada bit de salida de la reducción puede depender únicamente 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 establece que todas las clases de problemas NP-completos son isomorfos en tiempo polinomial. Es decir, si A y B son dos clases de problemas NP-completos, existe 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. utilizaron su equivalencia entre reducciones AC 0 y reducciones NC 0 para demostrar que todos los conjuntos completos para NP bajo reducciones AC 0 son isomorfos en tiempo polinomial . [ 6]
Una de las aplicaciones de los artilugios es la de demostrar la dificultad de los resultados de aproximación, reduciendo un problema que se sabe que es difícil de aproximar a otro problema cuya dificultad se debe demostrar. 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 las que es difícil determinar si una instancia dada tiene una función objetivo que está en el lado bajo o en el lado alto de la brecha. Las reducciones utilizadas en estas demostraciones y los artilugios utilizados en las reducciones deben preservar la existencia de esta brecha, y la solidez del resultado de inaproximabilidad derivado de la reducción dependerá de lo bien que se preserve la brecha.
Trevisan et al. (2000) formalizan el problema de encontrar gadgets que preserven la brecha, 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 por Garey, Johnson y Stockmeyer (1976), en la que el gadget que representa una cláusula 3-SAT consta de diez cláusulas 2-SAT, y en la que una asignación de verdad que satisface la cláusula 3-SAT también satisface al menos siete cláusulas en el gadget, mientras que una asignación de verdad que no satisface una cláusula 3-SAT tampoco satisface más de seis cláusulas del gadget. [8] Usando este gadget, y el hecho de que (a menos que P = NP ) no hay un esquema de aproximación de tiempo polinomial para maximizar el número de cláusulas 3-SAT que satisface una asignación de verdad, se puede demostrar que tampoco hay un esquema de aproximación para MAX 2-SAT.
Trevisan et al. muestran que, en muchos casos de los problemas de satisfacción de restricciones que estudian, los gadgets que conducen a los resultados de inaproximabilidad más fuertes posibles se pueden construir automáticamente, como la solución a un problema de programación lineal . Las mismas reducciones basadas en gadgets también se pueden usar 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. proporcionan un gadget ó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); utilizá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.