RE (complejidad)

En la teoría de la computabilidad y la teoría de la complejidad computacional , RE ( recursivamente enumerable ) es la clase de problemas de decisión para los cuales una máquina de Turing puede verificar una respuesta "sí" en un tiempo finito. ^{[ 1 ]} De manera informal, significa que si la respuesta a una instancia del problema es "sí", entonces existe algún procedimiento que tarda un tiempo finito en determinarla, y este procedimiento nunca informa falsamente "sí" cuando la respuesta verdadera es "no". Sin embargo, cuando la respuesta verdadera es "no", el procedimiento no tiene por qué detenerse; puede entrar en un " bucle infinito " para algunos casos de "no". Dicho procedimiento a veces se denomina semialgoritmo , para distinguirlo de un algoritmo , definido como una solución completa a un problema de decisión. ^{[ 2 ]}

De manera similar, co-RE es el conjunto de todos los lenguajes que son complementos de un lenguaje en RE . En cierto sentido, co-RE contiene lenguajes cuya pertenencia puede refutarse en un tiempo finito, pero demostrar la pertenencia podría llevar una eternidad.

De forma equivalente, RE es la clase de problemas de decisión para los cuales una máquina de Turing puede enumerar todas las instancias "sí", una por una (esto es lo que significa "enumerable"). Cada miembro de RE es un conjunto recursivamente enumerable y, por lo tanto, un conjunto diofántico .

Para demostrar que esto es equivalente, observe que si hay una máquina${\displaystyle E}$que enumera todas las entradas aceptadas, otra máquina que toma una cadena puede ejecutar${\displaystyle E}$y aceptar si la cadena está enumerada. Por el contrario, si una máquina${\displaystyle M}$acepta cuando una entrada está en un idioma, otra máquina puede enumerar todas las cadenas en el idioma intercalando simulaciones de${\displaystyle M}$en cada cadena de entrada y salida que se acepta (hay un orden de ejecución que eventualmente llegará a cada paso de ejecución porque hay una cantidad numerable de pares ordenados de entradas y pasos).

El conjunto de lenguajes recursivos ( R ) es un subconjunto tanto de RE como de co-RE . ^{[ 3 ]} De hecho, es la intersección de esas dos clases, porque podemos resolver cualquier problema para el cual exista un reconocedor y también un co-reconocedor simplemente intercalándolos hasta obtener un resultado. Por lo tanto:

${\displaystyle {\mbox{R}}={\mbox{RE}}\cap {\mbox{co-RE}}}$.

Por el contrario, el conjunto de lenguajes que no son ni RE ni co-RE se conoce como NRNC . Este es el conjunto de lenguajes para los que no se puede demostrar ni la pertenencia ni la no pertenencia en un tiempo finito, y contiene todos los demás lenguajes que no están ni en RE ni en co-RE . Es decir:

${\displaystyle {\mbox{NRNC}}={\mbox{ALL}}-({\mbox{RE}}\cup {\mbox{co-RE}})}$.

Estos problemas no solo son indecidibles, sino que ni ellos ni su complemento son recursivamente enumerables.

En enero de 2020, una preimpresión anunció una prueba de que RE era equivalente a la clase MIP* (la clase donde un verificador clásico interactúa con múltiples probadores cuánticos todopoderosos que comparten entrelazamiento ); ^{[ 4 ]} una prueba revisada, pero aún no completamente revisada, se publicó en Communications of the ACM en noviembre de 2021. La prueba implica que el problema de incrustación de Connes y el problema de Tsirelson son falsos. ^{[ 5 ]}

RE-completo es el conjunto de problemas de decisión que son completos para RE . En cierto sentido, estos son los problemas recursivamente enumerables "más difíciles". Generalmente, no se impone ninguna restricción a las reducciones utilizadas, excepto que deben ser reducciones de muchos a uno .

Ejemplos de problemas RE-completos:

1. Problema de parada : Si un programa, dado un número finito de datos de entrada, termina de ejecutarse o se ejecutará indefinidamente.
2. Según el teorema de Rice , decidir si una función pertenece a un subconjunto no trivial del conjunto de funciones recursivas parciales es un problema RE -difícil. Será completo siempre que el conjunto sea recursivamente enumerable.
3. John Myhill ( 1955 ) ^{[ 6 ]} demostró que todos los conjuntos creativos son RE -completos. 
4. El problema verbal uniforme para grupos o semigrupos . (De hecho, el problema verbal para algunos grupos individuales es RE -completo).
5. Decidir la pertenencia a una gramática formal general no restringida . (De nuevo, ciertas gramáticas individuales tienen problemas de pertenencia RE -completa).
6. El problema de validez para la lógica de primer orden .
7. Problema de correspondencia de publicaciones : Dada una lista de pares de cadenas, determine si existe una selección de estos pares (permitiendo repeticiones) tal que la concatenación de los primeros elementos (de los pares) sea igual a la concatenación de los segundos elementos.
8. Determinar si una ecuación diofántica tiene alguna solución entera.

co-RE-completo es el conjunto de problemas de decisión que son completos para co-RE . En cierto sentido, estos son los complementos de los problemas recursivamente enumerables más difíciles.

Ejemplos de problemas co-RE-completos:

1. El problema del dominó para las fichas de Wang .
2. El problema de satisfacibilidad para la lógica de primer orden .

• Algoritmo de completación de Knuth-Bendix
• Lista de problemas indecidibles
• Recursión polimórfica
• Algoritmo de Risch
• Semidecidibilidad