Gadget (informática)
En la teoría de la complejidad computacional , un dispositivo es un subconjunto de una instancia de problema que simula el comportamiento de una de las unidades fundamentales de un problema computacional diferente. Los gadgets se utilizan típicamente para construir reducciones de un problema computacional a otro, como parte de las pruebas de NP-completitud 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 "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 muchos-uno de la satisfacibilidad 3 , el problema de encontrar una asignación satisfactoria a una fórmula booleana que sea una conjunción (booleana y) de cláusulas, siendo cada cláusula la disyunción (booleana o) de tres términos, y cada término es una variable booleana o su negación. Una reducción de este problema a un problema difícil en gráficos no dirigidos , como el problema del ciclo de Hamilton o la coloración de gráficos ., normalmente se basaría en gadgets en forma de subgrafos que simulan el comportamiento de las variables y cláusulas de una determinada instancia de 3-satisfacibilidad. Estos dispositivos se pegarían luego para formar un solo gráfico, una instancia difícil para el problema del gráfico en consideración. [4]
Por ejemplo, el problema de probar la capacidad de 3 colores de los gráficos puede demostrarse NP-completo mediante una reducción de la capacidad de 3 colores de este tipo. La reducción utiliza dos vértices de gráficos especiales, etiquetados como "Suelo" 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 gadget 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 t0 , t 1 y t 2 , y al suelo y falsos vértices por los bordes que se muestran. Cualquier fórmula 3-CNF se puede convertir en un gráfico construyendo un gadget separado para cada una de sus variables y cláusulas y conectándolos como se muestra. [5]
En cualquier 3 coloración del gráfico resultante, uno puede designar los tres colores como verdadero, falso o fondo, donde falso y fondo son los colores dados a los vértices falso y terreno (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 de variable, solo son posibles dos colores: el vértice etiquetado con la variable debe ser de color verdadero o falso, y el vértice etiquetado con la negación de la variable debe ser de color falso o verdadero correspondientemente. De esta manera, las asignaciones válidas de colores a los gadgets variables se corresponden uno por uno con 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 3 colores válidos si al menos uno de sus vértices de términos adyacentes tiene el color verdadero, y no puede tener 3 colores si todos los vértices de los términos adyacentes tienen el color 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 y col. (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 solo de un número limitado de bits de la entrada, y utilizaron estas reducciones para probar un análogo de Berman –Conjetura de Hartmanis que establece que todos los conjuntos NP-completos son isomorfos en tiempo polinomial. [6]
