Reducción de muchos a uno

Tipo de reducción de Turing

En teoría de computabilidad y teoría de 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 ) a otro problema de decisión (si una instancia está en ) usando una función computable . La instancia reducida está en el lenguaje si y solo si la instancia inicial está en su lenguaje . 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 lo tanto, las reducciones se pueden usar para medir la dificultad computacional relativa de dos problemas. Se dice que 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 usar como parte de un programa (relativamente simple) que resuelve . ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$

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

Las reducciones de 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]

Definiciones

Lenguajes formales

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 solo si está en . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \Sigma }$ ${\displaystyle \Gamma }$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle f:\Sigma ^{*}\rightarrow \Gamma ^{*}}$ ${\displaystyle w}$ ${\displaystyle A}$ ${\displaystyle f(w)}$ ${\displaystyle B}$

Si tal función existe, se dice que es reducible a muchos-uno o m-reducible a y se escribe ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle A\leq _{\mathrm {m} }B.}$

Subconjuntos de números naturales

Dados dos conjuntos, uno dice que es reducible a muchos-uno y escribe ${\displaystyle A,B\subseteq \mathbb {N} }$ ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle A\leq _{\mathrm {m} }B}$

si existe una función computable total con si y solo si . ${\displaystyle f}$ ${\displaystyle x\in A}$ ${\displaystyle f(x)\in B}$

Si la reducción de muchos a uno es inyectiva , se habla de reducción uno a uno y se escribe . ${\displaystyle f}$ ${\displaystyle A\leq _{1}B}$

Si la reducción uno a uno es sobreyectiva , se dice que es recursivamente isomorfa a y se escribe ^{[4] p.324} ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle A\equiv B}$

Equivalencia de muchos a uno

Si ambos y , se dice que son muchos-uno equivalentes o m-equivalentes a y se escribe ${\displaystyle A\leq _{\mathrm {m} }B}$ ${\displaystyle B\leq _{\mathrm {m} }A}$ ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle A\equiv _{\mathrm {m} }B.}$

Completitud de muchos-uno (m-completitud)

Un conjunto se denomina completo muchos-uno , o simplemente m-completo , si y solo si es recursivamente enumerable y todo conjunto recursivamente enumerable es m-reducible a . ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Grados

La relación es en efecto una equivalencia , sus clases de equivalencia se llaman m-grados y forman un conjunto parcial con el orden inducido por . ^{[4] p.257} ${\displaystyle \equiv _{m}}$ ${\displaystyle {\mathcal {D}}_{m}}$ ${\displaystyle \leq _{m}}$

Algunas propiedades de los grados m, algunas de las cuales difieren de las propiedades análogas de los grados de Turing : ^{[4] pp.555--581}

• Hay un operador de salto bien definido en los m grados.
• El único grado m con salto 0 _m ′ es 0 _m .
• Hay m grados donde no existe donde . ${\displaystyle \mathbf {a} >_{m}{\boldsymbol {0}}_{m}'}$ ${\displaystyle \mathbf {b} }$ ${\displaystyle \mathbf {b} '=\mathbf {a} }$
• Todo orden lineal contable con un mínimo de elementos se incrusta en . ${\displaystyle {\mathcal {D}}_{m}}$
• La teoría de primer orden es isomorfa a la teoría de la aritmética de segundo orden. ${\displaystyle {\mathcal {D}}_{m}}$

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

El teorema de isomorfismo de Myhill puede enunciarse 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 1-grados . ${\displaystyle A,B}$ ${\displaystyle A\equiv B\iff A\equiv _{1}B}$ ${\displaystyle \equiv }$ ${\displaystyle \equiv _{1}}$ ${\displaystyle \equiv _{1}}$

Reducciones múltiples 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 polinomial, espacio logarítmico, mediante circuitos o proyecciones polilogarítmicas donde cada noción de reducción posterior es más débil que la anterior; consulte reducción en tiempo polinomial y reducción en espacio logarítmico para obtener más detalles. ${\displaystyle AC_{0}}$ ${\displaystyle NC_{0}}$

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

• 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) está cerrada bajo reducibilidad de muchos-uno si no existe reducción de un lenguaje fuera de C a un lenguaje en C. Si una clase está cerrada bajo reducibilidad de muchos-uno, entonces la reducción de muchos-uno puede usarse para mostrar que un problema está en C al reducirlo 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, incluyendo P , NP , L , NL , co-NP , PSPACE , EXP y muchas otras. Se sabe, por ejemplo, que las primeras cuatro de la lista están cerradas hasta la noción de reducción muy débil de proyecciones de tiempo polilogarítmicas. Sin embargo, estas clases no están cerradas bajo reducciones arbitrarias de muchos-uno.

Se extienden las reducciones de varios

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

Propiedades

• Las relaciones de reducibilidad de muchos a uno y de reducibilidad de 1 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 sólo si ${\displaystyle \mathbb {N} \setminus A\leq _{\mathrm {m} }\mathbb {N} \setminus B.}$
• Un conjunto es reducible en muchos-uno al problema de detención si y solo si es recursivamente enumerable . Esto indica que, con respecto a la reducibilidad en muchos-uno, el problema de detención es el más complicado de todos los problemas recursivamente enumerables. Por lo tanto, el problema de detención es recompleto. Nótese que no es el único problema recompleto.
• El problema de detención 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 decidibles ni m-completos y, por lo tanto, que existen máquinas de Turing no universales cuyos problemas de detención individuales son, no obstante, indecidibles .

Reducciones de Karp

Una reducción de muchos-uno en tiempo polinomial de un problema A a un problema B (los cuales normalmente se requieren que sean problemas de decisión ) es un algoritmo de tiempo polinomial para transformar las entradas del problema A en entradas del problema B , de modo 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-uno en tiempo polinomial también pueden conocerse como transformaciones polinomiales o reducciones de Karp , llamadas así por Richard Karp . Una reducción de este tipo se denota por o . ^{[6] [7]} ${\displaystyle A\leq _{m}^{P}B}$ ${\displaystyle A\leq _{p}B}$

Referencias

1. Abrahamson, Karl R. (primavera de 2016). "Reducciones de mapeo". CSCI 6420 – Computabilidad y complejidad . Universidad de Carolina del Este . Consultado el 12 de noviembre de 2021 .
2. EL Post, "Conjuntos enumerables recursivamente de números enteros positivos y sus problemas de decisión", Boletín de la Sociedad Matemática Americana 50 (1944) 284–316
3. Norman Shapiro, "Grados de computabilidad", Transactions of the American Mathematical Society 82 , (1956) 281–299
4. P. Odifreddi , Teoría de la recursión clásica: teoría de funciones y conjuntos de números naturales (p. 320). Estudios de lógica y fundamentos de las matemáticas, vol. 125 (1989), Elsevier 0-444-87295-7.
5. S. Ahmad, Incrustación del diamante en los grados de enumeración Σ 2 {\displaystyle \Sigma _{2}} (1991). Journal of Symbolic Logic , vol.56.
6. Goldreich, Oded (2008), Complejidad computacional: una perspectiva conceptual , Cambridge University Press, págs. 59-60, ISBN 9781139472746
7. Kleinberg, Jon ; Tardos, Éva (2006). Diseño de algoritmos . Educación Pearson. págs. 452–453. ISBN 978-0-321-37291-8.