RE (complexidade)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Merge-arrow 2.svg
Este artigo ou secção deverá ser fundido com Conjuntos recursivamente enumeráveis. (desde abril de 2013)
(por favor crie o espaço de discussão sobre essa fusão e justifique o motivo aqui; não é necessário criar o espaço em ambas as páginas, crie-o somente uma vez. Perceba que para casos antigos é provável que já haja uma discussão acontecendo na página de discussão de um dos artigos. Verifique ambas (1, 2) e não esqueça de levar toda a discussão quando levar o caso para a central.).

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.[1] 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[editar | editar código-fonte]

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

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

RE-completo[editar | editar código-fonte]

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)[3] 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[editar | editar código-fonte]

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[editar | editar código-fonte]

Referências

  1. Predefinição:CZoo
  2. Predefinição:CZoo
  3. Myhill, John (1955), "Creative sets", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 1: 97–108, doi:10.1002/malq.19550010205 .

Predefinição:Classes de complexidade

Ícone de esboço Este artigo sobre computação é um esboço. Você pode ajudar a Wikipédia expandindo-o.