RE (clase de complejidad)

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.