AEDs III 25/05/2011

// Hoje vamos falar mais sobre algoritimos NP-Completos

Revisando: Para provar que um problema é dificil basta provar que a solução do seu problema também soluciona um problema dificil.
           ou seja, pega a entrada de um problema NP-Completo mostre que pode ser mapeada para o seu problema, e que sua solução
           pode ser mapeada para a solução do problema NP-Completo novamente.

// Ela voltou a falar do problema de provar que o clique é equivalente ao problema de conjunto independente de vertices.
// E se um deles for NP-Completo, ambos são.

Lembre-se de provar primeiramente que o problema é NP e só depois provar que ele é NP-Completo.

Nota da Professora: NP-Difícil são os problemas NP-Completo sem a resposta de sim/não. Ou seja são a mesma coisa não simplificada.

CONCEITO:
Teorema de Cook
é o teorema que prova que qualquer problama NP-Completo pode ser convertido em qualquer outro problema NP-Completo

Nota da Professora: O conjunto de problema NP-Completo é um conjunto que cresce sempre que alguem consegue provar a tranformação
                    de um problema já pertencente ao conjunto em um novo problema.
                    O problema original é o problema do SAT que é àquele de se existe uma solução verdadeira para a expressão booleana
                    - NP-Incompleto são problemas que ninguem provou nem que é NP-Completo, nem provou que é Polinomial.

Nota da Professora: Existem problemas indecidíveis que são problemas como, "existe apenas K números primos?"
                    ou "Dado um programa qualquer ele pára para toda entrada? Ou entra em loop infinito?"
                    Bem uma observação pessoal minha é que para estes problemas, responder que "sim" ou "não" implica em explorar
                    um grupo de infinitas amostragens. Ou seja, é esse "infinito" que torna ele indecidível.