En la teoría de la computabilidad y la teoría de la complejidad computacional , una reducción de muchos uno es una reducción que convierte las instancias de un problema de decisión en instancias de un segundo problema de decisión. Por tanto, las reducciones se pueden utilizar para medir la dificultad computacional relativa de dos problemas. Se dice que A se reduce a B si, en términos sencillos, B es más difícil de resolver que A. Es decir, cualquier algoritmo que resuelve B también se puede usar como parte de un programa (por lo demás relativamente simple) que resuelve A.
Las reducciones de muchos uno son un caso especial y una forma más fuerte de reducciones de Turing . Con reducciones de muchos uno, el oráculo (es decir, nuestra solución para B) se puede invocar solo 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 necesario para 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 uno 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.
Las reducciones múltiples fueron utilizadas por primera vez por Emil Post en un artículo publicado en 1944. [1] Posteriormente, Norman Shapiro utilizó el mismo concepto en 1956 con el nombre de reducibilidad fuerte . [2]
Definiciones
Lenguajes formales
Suponer 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 es en si y solo si es en .
Si tal función existe, decimos que es muchos-uno reducible o m-reducible a y escribe
Si hay una función de reducción inyectiva muchos-uno, entonces decimos que A es 1-reducible o uno-uno reducible a y escribe
Subconjuntos de números naturales
Dados dos conjuntos decimos es muchos-uno reducible a y escribe
si existe una función computable total con Si adicionalmente es inyectivo decimoses 1-reducible a y escribe
Equivalencia muchos-uno y equivalencia 1
Si decimos es muchos-uno equivalente o m-equivalente a y escribe
Si decimos es 1-equivalente a y escribe
Completitud muchos-uno (completitud m)
Un conjunto se llama muchos-uno completo , o simplemente m-completo , si es recursivamente enumerable y cada conjunto recursivamente enumerable es m-reducible a .
Reducciones de muchos uno con limitaciones de recursos
Las reducciones de muchos uno a menudo están sujetas a restricciones de recursos, por ejemplo, que la función de reducción se puede calcular en tiempo polinómico o espacio logarítmico; ver transformación polinómica y la reducción log-espacio para más detalles.
Dados los problemas de decisión y y un algoritmo N que resuelve instancias de, podemos utilizar una reducción de muchos uno de a para resolver instancias de 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
Se dice que una clase C de las lenguas (o un subconjunto del conjunto potencia de los números naturales) es cerrado bajo mucho-uno reducibilidad si no existe una reducción de un idioma en el C a una lengua afuera C . Si una clase está cerrada bajo reducibilidad muchos-uno, entonces se puede usar la reducción muchos-uno para mostrar que un problema está en C reduciendo un problema en C a él. 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, incluyendo P , NP , L , NL , co-NP , PSPACE , EXP y muchas otras. Sin embargo, estas clases no se cierran bajo reducciones arbitrarias de muchos uno.
Propiedades
- Las relaciones de reducibilidad muchos-uno y reducibilidad 1 son transitivas y reflexivas y, por lo tanto, inducen un preorden en el conjunto de potencias de los números naturales.
- si y solo si
- Un conjunto es muchos-uno reducible al problema de la detención si y sólo si es recursivamente enumerable . Esto dice que con respecto a la reducibilidad muchos-uno, el problema de la detención es el más complicado de todos los problemas enumerables de forma recursiva. Por tanto, el problema de la detención se ha completado. Tenga en cuenta que no es el único problema completo.
- El problema de detención especializado para una máquina de Turing individual T (es decir, el conjunto de entradas para las que T finalmente se detiene) es de muchos-uno completo si T es una máquina de Turing universal . Emil Post demostró que existen conjuntos recursivamente enumerables que no son decidibles ni m-completos, y por lo tanto existen máquinas de Turing no universales cuyos problemas individuales de detención son, sin embargo, indecidibles .
Referencias
- ^ EL Post, " Conjuntos recursivamente enumerables de números enteros positivos y sus problemas de decisión ", Boletín de la American Mathematical Society 50 (1944) 284-316
- ^ Norman Shapiro, " Grados de computabilidad ", Transacciones de la American Mathematical Society 82 , (1956) 281-299