Reducción (complejidad) - Reduction (complexity)

Ejemplo de una reducción del problema de satisfacibilidad booleano ( AB ) ∧ (¬ A ∨ ¬ B ∨ ¬ C ) ∧ (¬ ABC ) a un problema de cobertura de vértices . Los vértices azules forman una cobertura mínima de vértices, y los vértices azules en el óvalo gris corresponden a una asignación de verdad satisfactoria para la fórmula original.

En la teoría de la computabilidad y la teoría de la complejidad computacional , una reducción es un algoritmo para transformar un problema en otro problema. Puede utilizarse una reducción suficientemente eficaz de un problema a otro para mostrar que el segundo problema es al menos tan difícil como el primero.

Intuitivamente, el problema A se puede reducir al problema B , si un algoritmo para resolver el problema B de manera eficiente (si existiera) también pudiera usarse como una subrutina para resolver el problema A de manera eficiente. Cuando esto es así, la solución A no puede ser más difícil de resolver B . "Más difícil" significa tener una estimación más alta de los recursos computacionales requeridos en un contexto dado (por ejemplo, mayor complejidad de tiempo , mayor requerimiento de memoria, necesidad costosa de núcleos de procesador de hardware adicionales para una solución paralela en comparación con una solución de un solo subproceso, etc.) . La existencia de una reducción de A a B , se puede escribir en la notación abreviada Am B , generalmente con un subíndice en el ≤ para indicar el tipo de reducción que se está utilizando (m: reducción de mapeo , p: reducción polinomial ).

La estructura matemática generada en un conjunto de problemas por las reducciones de un tipo particular generalmente forma un preorden , cuyas clases de equivalencia pueden usarse para definir grados de insolubilidad y clases de complejidad .

Introducción

Hay dos situaciones principales en las que necesitamos utilizar reducciones:

  • Primero, nos encontramos tratando de resolver un problema que es similar a un problema que ya hemos resuelto. En estos casos, a menudo una forma rápida de resolver el nuevo problema es transformar cada instancia del nuevo problema en instancias del problema anterior, resolverlas usando nuestra solución existente y luego usarlas para obtener nuestra solución final. Este es quizás el uso más obvio de las reducciones.
  • Segundo: supongamos que tenemos un problema que hemos demostrado que es difícil de resolver y tenemos un problema nuevo similar. Podríamos sospechar que también es difícil de resolver. Argumentamos por contradicción: supongamos que el nuevo problema es fácil de resolver. Entonces, si podemos demostrar que cada instancia del viejo problema puede resolverse fácilmente transformándola en instancias del nuevo problema y resolviéndolas, tenemos una contradicción. Esto establece que el nuevo problema también es difícil.

Un ejemplo muy simple de reducción es de multiplicar al cuadrado . Suponga que todo lo que sabemos hacer es sumar, restar, tomar cuadrados y dividir por dos. Podemos usar este conocimiento, combinado con la siguiente fórmula, para obtener el producto de dos números cualesquiera:

También tenemos una reducción en la otra dirección; obviamente, si podemos multiplicar dos números, podemos elevar al cuadrado un número. Esto parece implicar que estos dos problemas son igualmente difíciles. Este tipo de reducción corresponde a la reducción de Turing .

Sin embargo, la reducción se vuelve mucho más difícil si agregamos la restricción de que solo podemos usar la función de cuadratura una vez, y solo al final. En este caso, incluso si se nos permite usar todas las operaciones aritméticas básicas, incluida la multiplicación, no existe reducción en general, porque para obtener el resultado deseado como un cuadrado tenemos que calcular su raíz cuadrada primero, y este cuadrado La raíz podría ser un número irracional como el que no se puede construir mediante operaciones aritméticas con números racionales. Sin embargo, yendo en la otra dirección, ciertamente podemos elevar al cuadrado un número con solo una multiplicación, solo al final. Usando esta forma limitada de reducción, hemos mostrado el resultado nada sorprendente de que la multiplicación es más difícil en general que el cuadrado. Esto corresponde a una reducción de muchos uno .

Propiedades

Una reducción es un preorden , es decir, una relación reflexiva y transitiva , en P ( N ) × P ( N ), donde P ( N ) es el conjunto de potencias de los números naturales .

Tipos y aplicaciones de reducciones

Como se describe en el ejemplo anterior, hay dos tipos principales de reducciones que se utilizan en la complejidad computacional, la reducción muchos-uno y la reducción de Turing . Las reducciones de muchos-uno asignan instancias de un problema a instancias de otro; Las reducciones de Turing calculan la solución a un problema, asumiendo que el otro problema es fácil de resolver. La reducción de muchos uno es un tipo más fuerte de reducción de Turing y es más eficaz para separar los problemas en distintas clases de complejidad. Sin embargo, el aumento de las restricciones a las reducciones de muchos uno hace que sea más difícil encontrarlas.

Un problema está completo para una clase de complejidad si todos los problemas de la clase se reducen a ese problema, y ​​también está en la clase misma. En este sentido, el problema representa a la clase, ya que cualquier solución puede, en combinación con las reducciones, usarse para resolver todos los problemas de la clase.

Sin embargo, para que sean útiles, las reducciones deben ser fáciles . Por ejemplo, es muy posible reducir un problema NP-completo difícil de resolver como el problema de satisfacibilidad booleano a un problema trivial, como determinar si un número es igual a cero, haciendo que la máquina de reducción resuelva el problema en tiempo exponencial y produzca cero. solo si hay una solución. Sin embargo, esto no logra mucho, porque aunque podemos resolver el nuevo problema, realizar la reducción es tan difícil como resolver el problema anterior. Asimismo, una reducción calculando una función no computable puede reducir un problema indecidible a uno decidible. Como señala Michael Sipser en Introducción a la teoría de la computación : "La reducción debe ser fácil, en relación con la complejidad de los problemas típicos de la clase [...] Si la reducción en sí fuera difícil de calcular, una solución fácil para la completa problema no necesariamente daría una solución fácil a los problemas que se reducen a él ".

Por tanto, la noción apropiada de reducción depende de la clase de complejidad que se esté estudiando. Al estudiar la clase de complejidad NP y clases más difíciles como la jerarquía polinomial , se utilizan reducciones de tiempo polinómico . Al estudiar clases dentro de P como NC y NL , se utilizan reducciones de espacio logarítmico . Las reducciones también se utilizan en la teoría de la computabilidad para mostrar si los problemas son o no solucionables por máquinas; en este caso, las reducciones están restringidas solo a funciones computables .

En caso de problemas de optimización (maximización o minimización), a menudo pensamos en términos de reducción de preservación de aproximación . Supongamos que tenemos dos problemas de optimización tales que las instancias de un problema se pueden mapear en instancias del otro, de manera que las soluciones casi óptimas para las instancias del último problema se pueden transformar de nuevo para producir soluciones casi óptimas para el primero. De esta manera, si tenemos un algoritmo de optimización (o algoritmo de aproximación ) que encuentra soluciones casi óptimas (u óptimas) para instancias del problema B, y una reducción eficiente que preserva la aproximación del problema A al problema B, por composición obtenemos una optimización algoritmo que produce soluciones casi óptimas a instancias del problema A. Las reducciones que preservan la aproximación se utilizan a menudo para probar la dureza de los resultados de aproximación : si algún problema de optimización A es difícil de aproximar (bajo algún supuesto de complejidad) dentro de un factor mejor que α para algunos α, y hay una reducción que conserva la aproximación β del problema A al problema B, podemos concluir que el problema B es difícil de aproximar dentro del factor α / β.

Ejemplos de

Ejemplo detallado

El siguiente ejemplo muestra cómo utilizar la reducción del problema de la detención para demostrar que un idioma es indecidible. Suponga que H ( M , w ) es el problema de determinar si una máquina de Turing dada M se detiene (aceptando o rechazando) en la cadena de entrada w . Se sabe que este lenguaje es indecidible. Suponga que E ( M ) es el problema de determinar si el lenguaje que acepta una máquina de Turing dada M está vacío (en otras palabras, si M acepta alguna cadena). Se demuestra que E es indecidible por una reducción de H .

Para obtener una contradicción, supongamos que R es un partido decisivo para E . Usaremos esto para producir un decisor S para H (que sabemos que no existe). Entrada dada M y w (una máquina de Turing y algunos cadena de entrada), definen S ( M , w ) con el siguiente comportamiento: S crea una máquina de Turing N que acepta sólo si la cadena de entrada para N es w y M se detiene en la entrada w , y no se detiene de otra manera. El decisor S ahora puede evaluar R ( N ) para comprobar si el lenguaje aceptado por N está vacío. Si R acepta N , entonces el lenguaje aceptado por N está vacío, por lo que en particular M no se detiene en la entrada w , por lo que S puede rechazar. Si R rechaza N , entonces el lenguaje aceptado por N no está vacío, por lo que M se detiene en la entrada w , por lo que S puede aceptar. Por lo tanto, si tuviéramos un factor decisivo R para E , podríamos producir un factor decisivo S para el problema de detención H ( M , w ) para cualquier máquina M y entrada w . Como sabemos que tal S no puede existir, se deduce que el lenguaje E también es indecidible.

Ver también

Referencias

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein, Introducción a los algoritmos, MIT Press, 2001, ISBN  978-0-262-03293-3
  • Hartley Rogers, Jr .: Teoría de funciones recursivas y computabilidad efectiva, McGraw-Hill, 1967, ISBN  978-0-262-68052-3 .
  • Peter Bürgisser: Integridad y reducción en la teoría de la complejidad algebraica, Springer, 2000, ISBN  978-3-540-66752-0 .
  • ER Griffor: Manual de teoría de la computabilidad, Holanda Septentrional, 1999, ISBN  978-0-444-89882-1 .