Reduções

Questões-guia

1. O problema de resolver uma equação numérica de 1o. grau pode ser reduzido a resolver uma equação numérica de 2o. grau.  A fórmula de solução para equações de 2o. grau pode ser usada para resolver equações de 1o. grau?  Como?
2. Defina o que significa L₁ ≤_P L₂ para linguagens binárias L₁ e L₂.
3. O que se pode dizer de L₁ quando L₁ ≤_P L₂ e L₂ ∈ P?
4. Defina o que significa dizer que uma linguagem é NP-completa.  Como se define a classe NPC?
5. O que se pode dizer se houver uma linguagem L tal que L ∈ NPC e L ∈ P?
6. O que se pode dizer sobre NPC se P ≠ NP?
7. Defina o que significa dizer que uma linguagem é NP-difícil.
8. O que se pode dizer de L₂ quando L₁ ≤_P L₂ e L₁ ∈ NPC?

Exercícios:

1. Exercício 34.3-2 do Cormen.
2. Exercício 34.3-3 do Cormen.
3. Exercício 34.3-6 do Cormen.