reducción de muchos a uno

En la teoría de la computabilidad y la teoría de la complejidad computacional , una reducción muchos a 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${\displaystyle L_{1}}$) a otro problema de decisión (si una instancia está en${\displaystyle L_{2}}$) utilizando una función computable . La instancia reducida está en el lenguaje${\displaystyle L_{2}}$si y solo si la instancia inicial está en su idioma${\displaystyle L_{1}}$. Por lo tanto, si podemos decidir si${\displaystyle L_{2}}$Los ejemplos están en el idioma${\displaystyle L_{2}}$, podemos decidir si${\displaystyle L_{1}}$Los ejemplos están en el idioma${\displaystyle L_{1}}$aplicando la reducción y resolviendo para${\displaystyle L_{2}}$Por lo tanto, las reducciones pueden usarse para medir la dificultad computacional relativa de dos problemas. Se dice que${\displaystyle L_{1}}$se reduce a${\displaystyle L_{2}}$si, en términos sencillos${\displaystyle L_{2}}$es al menos tan difícil de resolver como${\displaystyle L_{1}}$Esto significa que cualquier algoritmo que resuelva${\displaystyle L_{2}}$También se puede utilizar como parte de un programa (por lo demás relativamente simple) que resuelve${\displaystyle L_{1}}$.

Las reducciones muchos a uno son un caso especial y una forma más fuerte de las reducciones de Turing . ^{[ 1 ]} Con las reducciones muchos a uno, el oráculo (es decir, nuestra solución para${\displaystyle L_{2}}$) se puede invocar solo una vez al final, y la respuesta no se puede modificar. Esto significa que si queremos mostrar ese problema${\displaystyle L_{1}}$puede reducirse a problema${\displaystyle L_{2}}$, podemos utilizar nuestra solución para${\displaystyle L_{2}}$solo una vez en nuestra solución para${\displaystyle L_{1}}$, a diferencia de las reducciones de Turing, donde podemos usar nuestra solución para${\displaystyle L_{2}}$tantas veces como sea necesario para resolver el problema de pertenencia para la instancia dada de${\displaystyle L_{1}}$.

Las reducciones muchos a uno fueron utilizadas por primera vez por Emil Post en un artículo publicado en 1944. ^{[ 2 ]} Posteriormente, Norman Shapiro utilizó el mismo concepto en 1956 bajo el nombre de reducibilidad fuerte . ^{[ 3 ]}

La relación${\displaystyle \equiv _{m}}$En efecto, es una equivalencia ; sus clases de equivalencia se denominan m-grados y forman un conjunto parcialmente ordenado (poset).${\displaystyle {\mathcal {D}}_{m}}$con el orden inducido por${\displaystyle \leq _{m}}$[ ^{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 un operador de salto bien definido en los m grados.
• El único grado m con salto 0 _m ′ es 0 _m .
• Hay m-grados${\displaystyle \mathbf {a} >_{m}{\boldsymbol {0}}_{m}'}$donde no existe${\displaystyle \mathbf {b} }$dónde${\displaystyle \mathbf {b} '=\mathbf {a} }$.
• Cada orden lineal contable con un elemento mínimo se incrusta en${\displaystyle {\mathcal {D}}_{m}}$.
• La teoría de primer orden de${\displaystyle {\mathcal {D}}_{m}}$es isomorfo a la teoría de la aritmética de segundo orden.

Hay una caracterización de${\displaystyle {\mathcal {D}}_{m}}$Como el único conjunto parcialmente ordenado que satisface varias propiedades explícitas de sus ideales , una caracterización similar ha eludido a los grados de Turing. ^{[ 4 ] pp.574-575}

El teorema de isomorfismo de Myhill se puede enunciar de la siguiente manera: "Para todos los conjuntos${\displaystyle A,B}$de números naturales,${\displaystyle A\equiv B\iff A\equiv _{1}B}$." Como corolario,${\displaystyle \equiv }$y${\displaystyle \equiv _{1}}$tienen las mismas clases de equivalencia. ^{[ 4 ] p.325} Las clases de equivalencia de${\displaystyle \equiv _{1}}$se denominan grados 1 .

Las reducciones de muchos a uno a menudo están sujetas a restricciones de recursos, por ejemplo, que la función de reducción sea computable en tiempo polinomial, espacio logarítmico, por${\displaystyle AC_{0}}$o${\displaystyle NC_{0}}$circuitos o proyecciones polilogarítmicas donde cada noción de reducción subsiguiente es más débil que la anterior; consulte la reducción en tiempo polinomial y la reducción en espacio logarítmico para obtener más detalles.

Dados los problemas de decisión${\displaystyle A}$y${\displaystyle B}$y un algoritmo N que resuelve instancias de${\displaystyle B}$, podemos usar una reducción de muchos a uno de${\displaystyle A}$a${\displaystyle B}$para resolver instancias de${\displaystyle A}$en:

• el tiempo necesario para N más el tiempo necesario para la reducción
• el máximo del espacio necesario para N y el espacio necesario para la reducción

Decimos que una clase C de lenguajes (o un subconjunto del conjunto potencia de los números naturales) es cerrada bajo reducibilidad muchos a uno si no existe ninguna reducción de un lenguaje fuera de C a un lenguaje en C. Si una clase es cerrada bajo reducibilidad muchos a uno, entonces la reducción muchos a uno puede usarse para demostrar que un problema está en C reduciéndolo a un problema en C. Las reducciones muchos a uno son valiosas porque la mayoría de las clases de complejidad bien estudiadas son cerradas bajo algún tipo de reducibilidad muchos a uno, incluyendo P , NP , L , NL , co-NP , PSPACE , EXP y muchas otras. Se sabe, por ejemplo, que las primeras cuatro enumeradas son cerradas salvo la noción de reducción muy débil de proyecciones de tiempo polilogarítmico. Sin embargo, estas clases no son cerradas bajo reducciones muchos a uno arbitrarias.

También se puede preguntar sobre casos generalizados de reducción muchos-uno. Un ejemplo de ello es la e-reducción , donde consideramos${\displaystyle f:A\to B}$que son recursivamente enumerables en lugar de restringirse a recursivamente${\displaystyle f}$La relación de reducibilidad resultante se denota${\displaystyle \leq _{e}}$y su conjunto parcialmente ordenado se ha estudiado de forma similar a como se ha hecho con los grados de Turing. Por ejemplo, existe un conjunto de saltos.${\displaystyle {\boldsymbol {0}}_{e}^{'}}$para los grados e . Los grados e admiten algunas propiedades que difieren de las del conjunto parcialmente ordenado de grados de Turing, por ejemplo, una incrustación del grafo diamante en los grados siguientes.${\displaystyle {\boldsymbol {'}}_{e}}$. ^{[ 5 ]}

• Las relaciones de reducibilidad muchos a uno y 1-reducibilidad son transitivas y reflexivas , y por lo tanto inducen un preorden en el conjunto potencia de los números naturales.
• ${\displaystyle A\leq _{\mathrm {m} }B}$si y solo si${\displaystyle \mathbb {N} \setminus A\leq _{\mathrm {m} }\mathbb {N} \setminus B.}$
• Un conjunto es reducible de muchos a uno al problema de la parada si y solo si es recursivamente enumerable . Esto significa que, en lo que respecta a la reducibilidad de muchos a uno, el problema de la parada es el más complejo de todos los problemas recursivamente enumerables. Por lo tanto, el problema de la parada es re-completo. Cabe destacar que no es el único problema re-completo.
• El problema de parada especializado para una máquina de Turing individual T (es decir, el conjunto de entradas para las cuales T finalmente se detiene) es completo en muchos-uno si y solo si T es una máquina de Turing universal . Emil Post demostró que existen conjuntos recursivamente enumerables que no son ni decidibles ni m-completos, y por lo tanto que existen máquinas de Turing no universales cuyos problemas de parada individuales son, sin embargo, indecidibles .

Una reducción de muchos a uno en tiempo polinomial de un problema A a un problema B (ambos generalmente requeridos como problemas de decisión ) es un algoritmo de tiempo polinomial para transformar las entradas del problema A en entradas del problema B , de manera que el problema transformado tenga la misma salida 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 a uno en tiempo polinomial también se conocen como transformaciones polinomiales o reducciones de Karp , llamadas así en honor a Richard Karp . Una reducción de este tipo se denota por${\displaystyle A\leq _{m}^{P}B}$o${\displaystyle A\leq _{p}B}$. ^{[ 6 ] [ 7 ]}