Redução por mapeamento

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita fontes fiáveis e independentes, mas que não cobrem todo o conteúdo. Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Trechos sem fontes poderão ser removidos.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing.

Na teoria da computabilidade e teoria da complexidade computacional, uma redução por mapeamento é uma redução que converte instâncias de um problema de decisão em instâncias de um outro problema de decisão. Reduções são, portanto, usado para medir a relativa dificuldade computacional de dois problemas.

Reduções por mapeamento são um caso especial e uma forma mais forte de redução. Reduções por mapeamento foram utilizados pela primeira vez por Emil Post em 1944. Mais tarde, em 1956, Norman Shapiro usou este mesmo conceito sob a redutibilidade.


Definições[editar | editar código-fonte]

Linguagem formal[editar | editar código-fonte]

Suponha que A e B são linguagens formais sobre os alfabetos Σ e Γ, respectivamente. Uma redução por mapeamento de A para B é uma função totalmente computável f : Σ* → Γ* que tem a propriedade de que cada palavra w está em A se e somente se f(w) está em B (isto é, A = f^{-1}(B)).

Se tal função f existe, dizemos que A é redutível por mapeamento para B e escrevemos

A \leq_m B.

Se houver uma função de redução por mapeamento injetora, então dizemos que A é redutível um a um para B e escrevemos

A \leq_1 B.

Subconjuntos dos números naturais[editar | editar código-fonte]

Dado dois conjuntos A,B \subseteq \mathbb{N} dizemos que A é redutível por mapeamento para B e escrevemos

A \leq_m B

Se existir uma função totalmente computável f with A = f^{-1}(B). Se adicionalmente f é injetora, dizemos que A é 1-redutível para B e escrevemos

A \leq_1 B.


Plenitude do mapeamento[editar | editar código-fonte]

Um conjunto B é chamado de mapeamento completo, sse B é recursivamente enumerável e cada conjunto recursivamente enumerável A é redutível por mapeamento a B.

Reduções por mapeamento e suas limitações de recursos[editar | editar código-fonte]

Reduções por mapeamento são muitas vezes sujeitos a restrições de recursos, por exemplo, a função de redução é computável em tempo polinomial ou espaço logarítmico.

Dado os problemas de decisão A e B e um algoritmo N, que resolve casos de B, podemos usar uma redução por mapeamento de A para B para resolver casos de A tal que:

  • O tempo será o tempo necessário para N mais o tempo necessário para a redução.
  • O espaço será o máximo do espaço necessário para N e o espaço necessário para a redução.

Dizemos que uma classe C de linguagens é fechada sob mapeamento, se não existe nenhuma redução a partir de uma linguagem em C para uma linguagem fora de C. Se uma classe é fechada sob mapeamento, uma redução por mapeamento pode ser usado para mostrar que um problema esta em C, reduzindo um problema de C para ele. Reduções por mapeamento são valiosas porque a maioria das classes de complexidade bem estudadas são fechados sob algum tipo de redutibilidade por mapeamento, incluindo P, NP, L, NL, co-NP, PSPACE, EXP, e muitas outras.

References[editar | editar código-fonte]