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.