RE (clase de complejidad)

La versión para imprimir ya no se admite y puede contener errores de representación. Actualiza los marcadores del navegador y utiliza en su lugar la función de impresión predeterminada del navegador.

En complejidad computacional, RE (abreviación de recursivamente enumerable) es la clase de complejidad conformada por aquellos problemas de decisión para los cuales una respuesta "sí" puede ser verificada por una máquina de Turing en una cantidad de tiempo finito.^[1] Informalmente, esto significa que si la respuesta es "sí", entonces existe algún procedimiento que toma tiempo finito para determinarla. Por otro lado, si la respuesta es "no", la máquina podría jamás detenerse. Equivalentemente, haciendo alusión a la palabra "enumerable", RE es la clase de los problemas de decisión para los cuales una máquina de Turing puede listar todas las instancias sí, una por una.

Análogamente, co-RE es el conjunto de todos los lenguajes que son complementos de un lenguaje en RE. En un sentido, co-RE contiene lenguajes cuyos miembros pueden ser rechazados en una cantidad de tiempo finito, pero que aceptarlos podría tardar para siempre.

Cada miembro de RE es un conjunto recursivamente enumerable, y así, un conjunto diofántico.

Relaciones con otras clases

RE es estrictamente mayor que la clase R, y estrictamente distinto de co-RE.^[2] Adicionalmente, se cumple que:

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

RE-completo

RE-completo es el conjunto de problemas de decisión que son completos para RE (en el mismo sentido que los NP-completos para NP). En cierto sentido, estos son los problemas recursivamente enumerables más "difíciles" (siguiendo la analogía, véase NP-hard). Todos estos problemas son no recursivos.

El problema de la parada es quizá el ejemplo más clásico de problema RE-completo.