Reducibilidad y grados de insolubilidad

La reducibilidad compara la dificultad de los problemas transformando uno en otro, y la agrupación de problemas de igual dificultad produce los grados de insolubilidad que estructuran el mundo más allá de lo computable.

Definition

Un problema se reduce a otro cuando un algoritmo con acceso a un solucionador para el segundo puede resolver el primero; los problemas que se reducen entre sí comparten un grado de insolubilidad, y estos grados forman un orden que mide la dificultad algorítmica relativa.

Scope

Este tema abarca la reducibilidad de muchos a uno y la reducibilidad de Turing, el uso de reducciones para probar la indecidibilidad, la operación de salto de Turing que produce problemas estrictamente más difíciles, la jerarquía aritmética que clasifica los problemas por complejidad lógica, y los resultados centrales de la teoría de grados como la existencia de grados intermedios.

Core questions

• ¿Cómo podemos decir que un problema irresoluble es más difícil que otro?
• ¿Cómo se utilizan las reducciones tanto para probar la indecidibilidad como para organizar los problemas?
• ¿Qué produce el salto de Turing y por qué es siempre estrictamente más difícil?
• ¿Existen problemas estrictamente entre lo decidible y el problema de la parada?

Key theories

Reducibilidad y el salto de Turing

La reducibilidad de Turing relaciona problemas mediante computación oráculo, y el salto de un problema, que codifica la parada en relación con él, es siempre estrictamente más difícil, generando una torre interminable de problemas cada vez más difíciles.

Existencia de grados intermedios

El teorema de Friedberg-Muchnik resolvió el problema de Post construyendo problemas computablemente enumerables que son indecidibles pero estrictamente más fáciles que el problema de la parada, utilizando el método de prioridad, lo que demuestra que los grados tienen una estructura rica.

Clinical relevance

La técnica de reducción es la herramienta cotidiana para probar que los problemas son irresolubles o, en la teoría de la complejidad, intratables: mostrar que un problema difícil conocido se reduce a uno nuevo transfiere la dificultad, que es exactamente cómo se establecen los resultados de indecidibilidad y NP-completitud en matemáticas y ciencias de la computación.

History

Turing introdujo las máquinas oráculo en 1939, y Post en 1944 enmarcó el estudio de los grados de insolubilidad y planteó el problema de si existían grados intermedios computablemente enumerables. Friedberg y Muchnik lo resolvieron independientemente en 1956-1957 inventando el método de prioridad, que se convirtió en una técnica central de la materia.

Key figures

• Emil Post
• Alan Turing
• Richard Friedberg
• Albert Muchnik

Seminal works

• soare2016
• rogers1987

Frequently asked questions

¿Qué es una reducción, intuitivamente?

Es una forma de resolver un problema utilizando un solucionador para otro. Si se puede traducir cualquier instancia del problema A en una instancia del problema B de modo que las respuestas coincidan, entonces B es al menos tan difícil como A, y una solución para B produce una solución para A.

¿Hay problemas más difíciles que el problema de la parada?

Sí, infinitos. Aplicar el salto de Turing al problema de la parada produce un problema estrictamente más difícil, y repetir la operación construye una jerarquía interminable, por lo que la insolubilidad se presenta en grados ilimitados en lugar de un solo nivel.