Saltar para o conteúdo

Redução por mapeamento

Origem: Wikipédia, a enciclopédia livre.

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.


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 é, ).

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

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

Subconjuntos dos números naturais

[editar | editar código-fonte]

Dado dois conjuntos dizemos que é redutível por mapeamento para e escrevemos

Se existir uma função totalmente computável with Se adicionalmente é injetora, dizemos que é 1-redutível para e escrevemos


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.