stringtranslate.com

Reducción de muchos a uno

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 .

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 .

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 .

Si tal función existe, se dice que es reducible a muchos-uno o m-reducible a y se escribe

Subconjuntos de números naturales

Dados dos conjuntos, uno dice que es reducible a muchos-uno y escribe

si existe una función computable total con si y solo si .

Si la reducción de muchos a uno es inyectiva , se habla de reducción uno a uno y se escribe .

Si la reducción uno a uno es sobreyectiva , se dice que es recursivamente isomorfa a y se escribe [4] p.324

Equivalencia de muchos a uno

Si ambos y , se dice que son muchos-uno equivalentes o m-equivalentes a y se escribe

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 .

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

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

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

El teorema de 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 1-grados .

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.

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:

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]

Propiedades

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]

Referencias

  1. ^ ab 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. ^ abcde 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.