RE (complexitat)

En teoria de la complexitat, la classe de complexitat RE és la classe dels problemes de decisió on la resposta SI es pot verificar amb una màquina de Turing en un temps finit.^[1] Això vol dir que si la resposta a un problema és SI, llavors hi ha cert procediment que tarda un temps finit en determinar-ho, i aquest procediment mai dona SI quan la resposta verdadera és NO. Tot i això, quan la resposta verdadera és NO, no cal que el procediment acabi, pot acabar en un bucle infinit per alguna casos de NO. Aquesta mena de procediments s'anomenen semialgorismes, per distingir-los dels algorismes, que es defineixen com una solució completa a un problema.^[2][3]

També es pot definir la classe RE com la classe de problemes de decisió pels quals una màquina de Turing pot llistar totes les instàncies que tenen sortida SI (per això es diu enumerable). Cada membre de la classe RE és un conjunt recursivament enumerable i per tant un conjunt diofàntic.

De manera similar, la classe co-RE és el conjunt de tots els llenguatges que son complements dels llenguatges de RE. D'alguna manera, co-RE conté els llenguatges dels quals si pertany a la classe es pot descartar en un temps finit, però provar que hi pertanyen pot portar un temps infinit.

El conjunt de llenguatges recursius (R) és un subconjunt tant de RE com de co-RE.^[4] De fet, és la intersecció d'aquestes dues classes, i per tant

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

RE-complet és el conjunt de problemes de decisió que son complets per RE. Són els problemes recursivament enumerables més difícils. Tots aquests problemes son no-recursius.

El problema més conegut RE-Complet és el problema de la parada.

La classe co-RE-complet és el conjunt de problemes de decisió que son complets per co-RE. Són els complementaris als problemes recursivament enumerables més difícils.