RE (clase de complejidad)

Carta Común · N.º 261812

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.​ 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í,…

Leer en Wikipedia