En la teoría de la computabilidad , se estudian muchas relaciones de reducibilidad (también llamadas reducciones , reducibilidades y nociones de reducibilidad ). Están motivados por la pregunta: conjuntos dados y de números naturales, ¿es posible convertir efectivamente un método para decidir la membresía en en un método para decidir la membresía en ? Si la respuesta a esta pregunta es afirmativa, entoncesse dice que es reducible a .
El estudio de las nociones de reductibilidad está motivado por el estudio de problemas de decisión . Para muchas nociones de reductibilidad, si cualquier conjunto no computable es reducible a un conjunto luego también debe ser no computable. Esto proporciona una técnica poderosa para demostrar que muchos conjuntos no son computables.
Relaciones de reducibilidad
Una relación de reducibilidad es una relación binaria en conjuntos de números naturales que es
- Reflexivo : cada conjunto es reducible a sí mismo.
- Transitivo : si un conjunto es reducible a un conjunto y es reducible a un conjunto luego es reducible a .
Estas dos propiedades implican que la reducibilidad es un preorden en el conjunto de potencias de los números naturales. Sin embargo, no todos los pedidos anticipados se estudian como nociones de reducibilidad. Las nociones estudiadas en la teoría de la computabilidad tienen la propiedad informal de que es reducible a si y solo si hay algún procedimiento de decisión (posiblemente no efectivo) para puede convertirse efectivamente en un procedimiento de decisión para . Las diferentes relaciones de reducibilidad varían en los métodos que permiten utilizar dicho proceso de conversión.
Grados de una relación de reducibilidad
Toda relación de reducibilidad (de hecho, todo preorden) induce una relación de equivalencia en el conjunto de potencias de los números naturales en la que dos conjuntos son equivalentes si y sólo si cada uno es reducible al otro. En la teoría de la computabilidad, estas clases de equivalencia se denominan grados de la relación de reducibilidad. Por ejemplo, los grados de Turing son las clases de equivalencia de conjuntos de naturales inducidos por la reducibilidad de Turing.
Los grados de cualquier relación de reducibilidad están ordenados parcialmente por la relación de la siguiente manera. Dejar ser una relación de reducibilidad y dejar y ser dos de sus grados. Luego si y solo si hay un conjunto en y un set en tal que . Esto es equivalente a la propiedad de que para cada conjunto en y cada set en , , porque dos conjuntos cualesquiera en C son equivalentes y dos conjuntos cualesquiera enson equivalentes. Es común, como se muestra aquí, usar la notación en negrita para denotar grados.
Reducibilidad de Turing
La noción de reducibilidad más fundamental es la reducibilidad de Turing . Un conjuntode números naturales es Turing reducible a un conjuntosi y solo si hay una máquina de Turing oráculo que, cuando se ejecuta concomo su conjunto de oráculo, calculará la función de indicador (función característica) de. Equivalentemente, es Turing reducible a si y solo si hay un algoritmo para calcular la función del indicador para siempre que el algoritmo cuente con un medio para responder correctamente a preguntas de la forma "¿Es en ? ".
La reducibilidad de Turing sirve como una línea divisoria para otras nociones de reducibilidad porque, según la tesis de Church-Turing , es la relación de reducibilidad más general la que es efectiva. Las relaciones de reducibilidad que implican la reducibilidad de Turing se conocen como reducibilidades fuertes , mientras que las que implica la reducibilidad de Turing son reducibilidades débiles. De manera equivalente, una relación de reducibilidad fuerte es aquella cuyos grados forman una relación de equivalencia más fina que los grados de Turing, mientras que una relación de reducibilidad débil es aquella cuyos grados forman una relación de equivalencia más burda que la equivalencia de Turing.
Reducciones más fuertes que la reducibilidad de Turing
Las fuertes reducibilidades incluyen
- Reducibilidad uno a uno : es uno a uno reducible a si hay una función uno a uno computable con para todos .
- Reducibilidad muchos-uno : es muchos-uno reducible a si hay una función computable con para todos .
- Tabla de la verdad reducible : es la tabla de verdad reducible a Si es Turing reducible a a través de una sola máquina de Turing (oráculo) que produce una función total relativa a cada oráculo.
- Tabla de verdad débil reducible : es la tabla de verdad débil reducible a si hay una reducción de Turing de a y una función computable que limita el uso . Cuando sea es la tabla de verdad reducible a , también es una tabla de verdad débil reducible a , ya que se puede construir un límite computable sobre el uso considerando el uso máximo sobre el árbol de todos los oráculos, que existirá si la reducción es total en todos los oráculos.
- Reducible positivo: es positivo reducible a si y solo si es la tabla de verdad reducible a de una manera que se pueda calcular para cada una fórmula que consta de átomos de la forma de tal manera que estos átomos se combinan por y y o, donde el y de y es 1 si y y así.
- Reducibilidad de enumeración : similar a la reducibilidad positiva, relacionada con el procedimiento efectivo de enumerabilidad de a .
- Disyuntivo reducible: similar al reducible positivo con la restricción adicional de que solo se permiten o.
- Reducibilidad conjuntiva: similar a la reducibilidad positiva con la restricción adicional de que solo se permiten y.
- Reducibilidad lineal: similar a la reducibilidad positiva pero con la restricción de que todos los átomos de la forma se combinan por exclusivos o . En otras palabras, es lineal reducible a si y solo si una función computable calcula para cada un conjunto finito dado como una lista explícita de números tales que si y solo si contiene un número impar de elementos de .
Muchos de estos fueron introducidos por Post (1944). Post buscaba un conjunto no computable y computablemente enumerable al que Turing no podía reducir el problema de la detención . Como no pudo construir un conjunto de este tipo en 1944, trabajó en los problemas análogos para las diversas reducibilidades que introdujo. Desde entonces, estas reducibilidades han sido objeto de mucha investigación y se conocen muchas relaciones entre ellas.
Reducibilidades limitadas
Se puede definir una forma acotada de cada una de las fuertes reducibilidades anteriores. El más famoso de ellos es la reducción de la tabla de verdad acotada, pero también hay Turing acotado, tabla de verdad débil acotada y otros. Estos tres primeros son los más comunes y se basan en el número de consultas. Por ejemplo, un conjunto es una tabla de verdad acotada reducible a si y solo si la maquina de Turing informática relativo a calcula una lista de hasta números, consultas en estos números y luego termina para todas las posibles respuestas de oráculo; el valor es una constante independiente de . La diferencia entre la tabla de verdad débil acotada y la reducción de Turing acotada es que en el primer caso, hastalas consultas deben realizarse al mismo tiempo, mientras que en el segundo caso, las consultas se pueden realizar una tras otra. Por esa razón, hay casos en los que está limitado Turing reducible a pero no una tabla de verdad débil reducible a .
Fuertes reducciones en la complejidad computacional
Las fuertes reducciones enumeradas anteriormente restringen la forma en que se puede acceder a la información de Oracle mediante un procedimiento de decisión, pero no limitan de otra manera los recursos computacionales disponibles. Por tanto, si un conjuntoes decidible entonces es reducible a cualquier conjunto bajo cualquiera de las fuertes relaciones de reductibilidad enumeradas anteriormente, incluso si no es decidible en tiempo polinomial o tiempo exponencial. Esto es aceptable en el estudio de la teoría de la computabilidad, que está interesada en la computabilidad teórica, pero no es razonable para la teoría de la complejidad computacional , que estudia qué conjuntos pueden decidirse bajo ciertos límites de recursos asintóticos.
La reducibilidad más común en la teoría de la complejidad computacional es la reducibilidad en tiempo polinomial ; un conjunto A es reducible en tiempo polinomial a un conjuntosi hay una función de tiempo polinomial f tal que para cada, es en si y solo si es en . Esta reducibilidad es, esencialmente, una versión limitada por recursos de la reducibilidad muchos-uno. Otras reducibilidades limitadas por recursos se utilizan en otros contextos de la teoría de la complejidad computacional donde otros límites de recursos son de interés.
Reducciones más débiles que la reducibilidad de Turing
Aunque la reducibilidad de Turing es la reducibilidad más general que es efectiva, comúnmente se estudian las relaciones de reducibilidad más débiles. Estas reducibilidades están relacionadas con la definibilidad relativa de los conjuntos sobre la aritmética o la teoría de conjuntos. Incluyen:
- Reducibilidad aritmética : un conjunto es aritmético en un conjunto Si es definible sobre el modelo estándar de la aritmética de Peano con un predicado adicional para. De manera equivalente, de acuerdo con el teorema de Post , A es aritmética en si y solo si es Turing reducible a , la el salto de Turing de, por algún número natural . La jerarquía aritmética da una clasificación más fina de reducibilidad aritmética.
- Reducibilidad hiperaritmética : un conjunto es hiperaritmético en un conjunto Si es definible (ver jerarquía analítica ) sobre el modelo estándar de la aritmética de Peano con un predicado para. Equivalentemente, es hiperaritmético en si y solo si es Turing reducible a , la el salto de Turing de, para algunos - ordinal recursivo .
- Constructibilidad relativa : un conjunto es relativamente construible a partir de un conjunto Si es en , el modelo transitivo más pequeño de la teoría de conjuntos ZFC que contiene y todos los ordinales.
Referencias
- K. Ambos-Spies y P. Fejer, 2006. " Grados de insolubilidad ". Preimpresión inédita.
- P. Odifreddi, 1989. Teoría de la recursividad clásica , Holanda Septentrional. ISBN 0-444-87295-7
- P. Odifreddi, 1999. Teoría de la recursión clásica, Volumen II , Elsevier. ISBN 0-444-50205-X
- E. Post, 1944, "Conjuntos recursivamente enumerables de números enteros positivos y sus problemas de decisión", Boletín de la American Mathematical Society , volumen 50, páginas 284–316.
- H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability , segunda edición 1987, MIT Press. ISBN 0-262-68052-1 ( tapa blanda), ISBN 0-07-053522-1
- G Sacks, 1990. Teoría de la recursividad superior , Springer-Verlag. ISBN 3-540-19305-7