reducción de muchos uno

Tipo de reducción de Turing

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 efectiva. 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 . ${\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 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 . ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$

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]

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 sólo 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 reducible a m y se escribe ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle B}$

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

Subconjuntos de números naturales

Dados dos conjuntos, se dice que son muchos reducibles a y se 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 iff . ${\displaystyle f}$ ${\displaystyle x\in A}$ ${\displaystyle f(x)\in B}$

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

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

${\displaystyle A\equiv B}$

Equivalencia de muchos uno

Si ambos y , se dice que es equivalente a muchos uno o equivalente a m 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 (completitud m)

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 . ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Grados

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} ${\displaystyle \equiv _{m}}$ ${\displaystyle {\mathcal {D}}_{m}}$ ${\displaystyle \leq _{m}}$

Algunas propiedades de los grados m, algunas de las cuales difieren de 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 dónde . ${\displaystyle \mathbf {a} >_{m}{\boldsymbol {0}}_{m}'}$ ${\displaystyle \mathbf {b} }$ ${\displaystyle \mathbf {b} '=\mathbf {a} }$
• Cada orden lineal contable con un elemento mínimo se integra 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 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} ${\displaystyle {\mathcal {D}}_{m}}$

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 . ${\displaystyle A,B}$ ${\displaystyle A\equiv B\iff A\equiv _{1}B}$ ${\displaystyle \equiv }$ ${\displaystyle \equiv _{1}}$ ${\displaystyle \equiv _{1}}$

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 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. ${\displaystyle AC_{0}}$ ${\displaystyle NC_{0}}$

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: ${\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 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.

Se amplían las reducciones 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] ${\displaystyle f:A\to B}$ ${\displaystyle f}$ ${\displaystyle \leq _{e}}$ ${\displaystyle {\boldsymbol {0}}_{e}^{'}}$ ${\displaystyle {\boldsymbol {'}}_{e}}$

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.
• ${\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 muchos uno al problema de detención si y sólo si es recursivamente enumerable . Esto dice que con respecto a la reducibilidad de muchos uno, el problema de detención es el más complicado de todos los problemas recursivamente enumerables. De este modo se vuelve a completar el problema de la detención. Tenga en cuenta que no es el único problema de recompletar.
• 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 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 tanto, que existen máquinas de Turing no universales cuyos problemas de detención individuales son, sin embargo, indecidibles .

reducciones de karp

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 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]} ${\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 recursivamente enumerables de números enteros positivos y sus problemas de decisión", Boletín de la American Mathematical Society 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 clásica de la recursión: la 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, Incrustando el diamante en los grados de enumeración Σ 2 {\displaystyle \Sigma _{2}} (1991). Revista de Lógica Simbólica, 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.