Redução por mapeamento

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

Linguagem formal

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

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

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

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

• E. L. Post, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society 50 (1944) 284-316
• Norman Shapiro, "Degrees of Computability", Transactions of the American Mathematical Society 82, (1956) 281-299