En teoría de computabilidad y teoría de la complejidad computacional , una reducción de muchos uno (también llamada reducción de mapeo [1] ) es una reducción que convierte instancias de un problema de decisión (si una instancia está en ) en otro problema de decisión (si una instancia está en ) utilizando una función computable . La instancia reducida está en el idioma si y sólo si la instancia inicial está en su idioma . Por lo tanto, si podemos decidir si las instancias están en el lenguaje , podemos decidir si las instancias están en su lenguaje aplicando la reducción y resolviendo para . Por tanto, las reducciones se pueden utilizar para medir la dificultad computacional relativa de dos problemas. Se dice que se reduce a si, en términos sencillos, es al menos tan difícil de resolver como . Esto significa que cualquier algoritmo que resuelva también se puede utilizar como parte de un programa (por lo demás relativamente simple) que resuelva .
Las reducciones de muchos uno son un caso especial y una forma más fuerte de reducciones de Turing . [1] Con reducciones de muchos uno, el oráculo (es decir, nuestra solución para ) se puede invocar solo una vez al final y la respuesta no se puede modificar. Esto significa que si queremos demostrar que el problema se puede reducir a problema , podemos usar nuestra solución solo una vez en nuestra solución para , a diferencia de las reducciones de Turing, donde podemos usar nuestra solución tantas veces como sea necesario para resolver el problema de membresía para la instancia dada de .
Emil Post utilizó por primera vez las reducciones de muchos uno en un artículo publicado en 1944. [2] Posteriormente, Norman Shapiro utilizó el mismo concepto en 1956 bajo el nombre de reducibilidad fuerte . [3]
Supongamos que y son lenguajes formales sobre los alfabetos y , respectivamente. Una reducción de muchos uno de a es una función computable total que tiene la propiedad de que cada palabra está en si y sólo si está en .
Si tal función existe, se dice que es reducible a muchos uno o reducible a m y se escribe
Dados dos conjuntos, se dice que son muchos reducibles a y se escribe
si existe una función computable total con iff .
Si la reducción muchos-uno es inyectiva , se habla de reducción uno-uno y se escribe .
Si la reducción uno a uno es sobreyectiva , se dice que es recursivamente isomorfa y se escribe [4] p.324
Si ambos y , se dice que es equivalente a muchos uno o equivalente a m y se escribe
Un conjunto se llama muchos-uno completo , o simplemente m-completo , si y solo si es recursivamente enumerable y cada conjunto recursivamente enumerable es m-reducible a .
La relación de hecho es una equivalencia , sus clases de equivalencia se llaman m-grados y forman un poset con el orden inducido por . [4] pág.257
Algunas propiedades de los grados m, algunas de las cuales difieren de propiedades análogas de los grados de Turing : [4] pp.555--581
Existe una caracterización de que el poset único satisface varias propiedades explícitas de sus ideales ; una caracterización similar ha eludido los grados de Turing. [4] págs.574--575
El teorema del isomorfismo de Myhill se puede enunciar de la siguiente manera: "Para todos los conjuntos de números naturales, ". Como corolario, y tienen las mismas clases de equivalencia. [4] p.325 Las clases de equivalencias de se denominan grados 1 .
Las reducciones de muchos uno a menudo están sujetas a restricciones de recursos, por ejemplo, que la función de reducción es computable en tiempo polinómico, espacio logarítmico, por circuitos o proyecciones polilogarítmicas donde cada noción de reducción posterior es más débil que la anterior; consulte reducción de tiempo polinomial y reducción de espacio logarítmico para obtener más detalles.
Dados los problemas de decisión y un algoritmo N que resuelve instancias de , podemos usar una reducción de muchos uno desde a para resolver instancias de en:
Decimos que una clase C de lenguas (o un subconjunto del conjunto potencia de los números naturales) está cerrada bajo reducibilidad muchos uno si no existe ninguna reducción de una lengua fuera de C a una lengua en C. Si una clase está cerrada bajo reducibilidad de muchos uno, entonces se puede usar la reducción de muchos uno para mostrar que un problema está en C reduciéndolo a un problema en C. Las reducciones de muchos uno son valiosas porque la mayoría de las clases de complejidad bien estudiadas están cerradas bajo algún tipo de reducibilidad de muchos uno, incluidas P , NP , L , NL , co-NP , PSPACE , EXP y muchas otras. Se sabe, por ejemplo, que los primeros cuatro enumerados están cerrados a la muy débil noción de reducción de las proyecciones de tiempo polilogarítmicas. Sin embargo, estas clases no están cerradas bajo reducciones arbitrarias de muchos uno.
También cabe preguntar acerca de los casos generalizados de reducción de muchos uno. Un ejemplo de ello es la reducción electrónica , donde consideramos que son recursivamente enumerables en lugar de restringirlos a recursivos . La relación de reducibilidad resultante se denota y su poset se ha estudiado de manera similar a la de los grados de Turing. Por ejemplo, hay un conjunto de saltos para e -grados. Los grados e admiten algunas propiedades que difieren de las del poset de grados de Turing, por ejemplo, una incrustación del gráfico de diamantes en los grados siguientes . [5]
Una reducción de muchos en tiempo polinomial de un problema A a un problema B (generalmente se requiere que ambos sean problemas de decisión ) es un algoritmo de tiempo polinomial para transformar entradas al problema A en entradas al problema B , de modo que las transformadas El problema tiene el mismo resultado que el problema original. Una instancia x del problema A se puede resolver aplicando esta transformación para producir una instancia y del problema B , dando y como entrada a un algoritmo para el problema B y devolviendo su salida. Las reducciones de muchos uno en tiempo polinomial también pueden conocerse como transformaciones polinómicas o reducciones de Karp , que llevan el nombre de Richard Karp . Una reducción de este tipo se denota por o . [6] [7]