RE (complexidade)

 Nota: Não confundir com Conjuntos recursivamente enumeráveis.

Em Teoria da Computabilidade e na Teoria da Complexidade Computacional, RE (recursivamente enumerável) é uma classe de problemas de decisão onde uma resposta "sim" pode ser verificada por uma máquina de Turing em uma quantidade finita de tempo. Informalmente, isto significa que se a resposta é "sim", então existe algum procedimento que leva um tempo finito para determinar isso. Por outro lado, se a resposta é "não", a máquina poderá nunca parar. Equivalentemente, RE é uma classe de problemas de decisão para que uma máquina de Turing pode listar todas as instâncias "sim", uma por uma (isto é o que 'enumerável' significa).

Similarmente, co-RE é o conjunto de todas as linguagens que são complementos de uma linguagem em RE. De certo modo, co-RE contém linguagens em que a pertinência pode ser refutada em uma quantidade finita de tempo, mas provar a pertinência poderá levar uma eternidade.

Cada membro de RE é um recursivamente enumerável e, portanto, um conjunto diofantino.

Relações com outras classes

O conjunto das linguagens recursivas (R) é um subconjunto de ambas RE e co-RE. De fato, é a intersecção dessas duas classes:

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

RE-completo

RE-completo é um conjunto de problemas de decisão que são completos para RE. De certo modo, estes são os mais "difíceis" problemas recursivamente enumeráveis. Todos esses problemas são não recursivos. Geralmente, nenhuma restrição é colocada sobre as reduções usadas exceto que elas sejam reduções por mapeamento.

Exemplos de problemas RE-completo:

1. Problema da parada: Determinar se um programa para a partir de uma dada entrada ou se ele continuará rodando para sempre.
2. Pelo Teorema de Rice, decidir a pertinência em qualquer subconjunto não-trivial do conjunto de funções recursivas é RE-hard. Isto será completo quando o conjunto for recursivamente enumerável.
3. John Myhill (1955) provou que todos os conjuntos criativos e produtivos são RE-completo.
4. A uniformidade do problema da palavra para grupos ou semigrupos. [Na verdade, o problema da palavra para alguns grupos individuais é RE-completo.]
5. Decidir a pertinência em uma gramática formal irrestrita geral. [Novamente,algumas gramáticas individuais têm problema de pertinência RE-completo.]
6. O problema de validade para a lógica de primeira ordem.
7. Problema da correspondência de Post: Dado um conjunto finito de palavras, determinas se existe uma palavra que pode ser formada em uma composição de palavras (permitindo repetição) em dois diferentes modos.
8. Determinar se uma equação diofantina tem alguma solução inteira.

co-RE-completo

co-RE-completo é um conjunto de problemas de decisão que são completos para co-RE. De certo modo, estes são os complementos dos mais difíceis problemas recursivamente enumeráveis.

Exemplos de problemas co-RE-completo:

1. O problema do dominó para o dominó de Wang.
2. O problema da satisfabilidade para lógica de primeira ordem.

Ver também

• Lista de problemas indecidíveis