Reducción de muchos a uno

En la teoría de la computabilidad y la teoría de la complejidad computacional , una reducción de muchos a uno (también llamada reducción de mapeo ^[1] ) es una reducción que convierte instancias de un problema de decisión en instancias de un segundo problema de decisión donde la instancia reducida a está en el lenguaje si el la instancia inicial estaba en su idioma y no está en el idioma si la instancia inicial no estaba en su idioma . Por 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 ${\ estilo de visualización L_ {1}}$ ${\ estilo de visualización L_ {2}}$ ${\ estilo de visualización L_ {2}}$ ${\ estilo de visualización L_ {1}}$ ${\ estilo de visualización L_ {2}}$ ${\ estilo de visualización L_ {1}}$ ${\ estilo de visualización L_ {2}}$ ${\ estilo de visualización L_ {2}}$ ${\ estilo de visualización L_ {1}}$ ${\ estilo de visualización L_ {2}}$ . Por lo tanto, las reducciones se pueden usar para medir la dificultad computacional relativa de dos problemas. Se dice que se reduce a si, en términos sencillos, es más difícil de resolver que . Es decir, cualquier algoritmo que resuelva también se puede usar como parte de un programa (por lo demás relativamente simple) que resuelva . ${\ estilo de visualización L_ {1}}$ ${\ estilo de visualización L_ {2}}$ ${\ estilo de visualización L_ {2}}$ ${\ estilo de visualización L_ {1}}$ ${\ estilo de visualización L_ {2}}$ ${\ estilo de visualización L_ {1}}$

Las reducciones muchos-uno son un caso especial y una forma más fuerte de reducciones de Turing . ^[1] Con las reducciones de muchos a uno, el oráculo (es decir, nuestra solución para B) solo se puede invocar una vez al final y la respuesta no se puede modificar. Esto significa que si queremos mostrar que el problema A se puede reducir al problema B, podemos usar nuestra solución para B solo una vez en nuestra solución para A, a diferencia de la reducción de Turing, donde podemos usar nuestra solución para B tantas veces como necesarios al resolver A.

Esto significa que las reducciones de muchos-uno asignan instancias de un problema a instancias de otro, mientras que 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 a uno es más eficaz para separar los problemas en distintas clases de complejidad. Sin embargo, el aumento de las restricciones en las reducciones de muchos hace que sea más difícil encontrarlas.

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