AEDs III 18/05/2011

// A aula de hoje é sobre problemas NP-Completos

CONCEITO:
NP são os problemas cuja a solução é Non-deterministic Polinomial, ou seja não deterministicamente é polinômial.
Na prática isso significa que a solução pode ou não ser exponencial.
Portando as que não são exponenciais pertencem ao sub-conjunto de NP que é P ou Polinomiais.
Àquelas que são comprovadamente exponenciais pertencem ao grupo NP-Completo.

Nota da Professora:
 Na verdade não foi provado até hoje que os NP-Completos não possuem solução polinomial.
 Porem já foi provado que se encontrarmos uma solução para um deles, encontramos uma solução para TODOS eles,
 pois eles podem ser facilmente mapeados uns nos outros.

Para a maioria destes problemas existem mapeamentos para soluções polinomiais.
Portanto na prática a maioria dos NP tem solução Polinomial.
A duvida é sobre esse grupo restante que não se conseguiu encontrar solução polinomial.
Acredita-se que este grupo restante possa ser divido entre os conjunto NP-Completo e P.

// Nota: por questões teoricas, os problemmas definidos aqui são todos problemas de sim/não
//       ou seja ao invés de "Qual o menor caminho de A a B",
//       o programa é convertido para "Existe um caminho de comprimento K entre A e B? sim ou não?"

// Nota2: Algum desses teoricos doidos da computação ainda inventou um nome para os problemas NP-Completos
//        que não estão formatados nesse formato de sim/não. Ele chamou estes problemas de NP-Dificil,
//        mas é um nome completamente desnecessário já que é a mesma coisa que NP-Completo, só falta transformar.

// imagino q tb deve ter um otro nome estranho pros polinomiais que não foram formatados ainda xP

CONCEITO:
NP-Completo é exatamente a sub-classe de NP que não tem solução polinomial de maneira alguma.
Não se sabe se essa classe existe mesmo, mas tem premios pra quem conseguir provar que sim ou que não.
Só que ninguem consegue provar isso a anos. . .

CONCEITO:
Problemas Sim/Não -> é uma simplificação de problemas genericos para fins teóricos.
Por exemplo o problema do caixeiro viajante pode virar um destes se eu perguntar "existe uma solução de tamanho menor q K?"

Nota Repetida (pq ja falei ali encima):
Por definição para fins teóricos os problemas NP-Completo são modelados todos em modelos Sim/Não.

// nota: deve-se ter uma base de problemas faceis e dificeis para voce conseguir ao encontrar um problema novo poder
//       entender se é ou não um problema difícil por via de comparação.

CONCEITO:
Problema de coloração de grafos:
Qual o menor número de cores que consigo usar para colorir um grafo de forma que dois vertices adjacentes não tenham a mesma cor?
Voce pode pensar nisso para vários mapeamentos. Por exemplo cada vertice um professor, cada cor uma sala,
e os vertices os tempos em que os professores vão usar as salas.
PS: isso é NP completo
PS: se isso for existe possibilidade de colorir com duas cores? sim/nao, isso vira polinomial.

CONCEITO:
Ciclo de Hamilton é um ciclo que passa por todos os nós.

Problema NP-completo: Existe ciclo de hamilton?

Fácil para grau no maximo 2, dificil para graus maiores que 2

CONCEITO:
cobertura de arestas.
qual o mínimo de arestas que eu posso usar para ter ao menos uma aresta para cada vertice.

CONCEITO:
Cobertura de vertices:
Qual o mínimo de vertices que posso usar para garantir que cada aresta tera contato com ao menos um vertice.
NP COMPLETO

// Nota esses problemas devem ser encaixados no modelo sim/nao, mas a professora ta falando rapido entao nao consegui modelar aqui.


CONCEITO:
Algoritimos não deterministas são algoritimos que realizam operações "magicas", ou seja toma uma decisão sem realizar um cálculo
propriamente dito é mais como deus dizendo pra ele onde ir.


CONCEITO:
A operação Escolhe é uma operação não deterministica que sempre que voce encontra uma encruzilhada, uma dúvida, voce consegue
descobrir o caminho certo com esse método em O(1), devido aos seus contatos divinos magicos =].

// Note que não-determinismo é um conceito puramente teorico.
// Voce pode pensar que essa historia de escolhe é pensar que deus te ajuda a evitar backtrackings exponenciais.
// Pensando de outra maneira equivalente: O metodo escolhe te dá sempre uma subestrutura ótima
// permitindo que voce tome uma decisão local =]. O metodo escolhe só falha se não houver solução.

CONCEITO:
Problema de Satisfabilidade.
É o problema de verificar se uma expressão com N váriaveis booleanas pode ser igual a 1 ou não.
Basicamente voce tem que tentar todas as permutações das N variaveis pra saber se é possível ou não.

Esse é o primeiro problema que foi provado ser dificil.

Solução determinista é O(2^n)
Com o metodo escolha é O(n)

CONCEITO:
Como saber se é NP?
Basta mostrar que 1: existe algoritmo nao determinista que soluciona, 2: existe um algoritimo polinomial que verifica solução.

CONCEITO:
Tranformação polinomial é tranformar a entrada de um programa p1 em uma entrada de um programa p2
de modo que a saida de p2 possa ser tranformada de volta gerando a saída correta de p1 com tal entrada.
Note que ambas as tranformações devem ser de O(polinomial) para serem validas.
Se voce arrumar uma NP para tranformar isso, então não é uma tranformação polinomial e não vai ser vir pros propósitos abaixo:

Tranformar um problema em um problema NP não prova nada
Mas transformar um problema NP em um outro problema que voce nao sabe a complexidade ainda, indica que esse outro problema é NP.

Ou seja, posso usar isso como prova para mostrar que P2 é NP, basta escolher um NP para P1 e mostrar que é possível tranformar.

CONCEITO:
Um grafo transposto é um grafo que possui todas as transições possíveis menos as transições do grafo original.
É como o negativo das transições do grafo.
Isso é O(V²)

CONCEITO:
Conjunto independente de um grafo é um conjunto de nós que não possuem arestas entre sí.
Problema existe um conjunto independente >= k? sim/nao?
Ou ainda, qual o maior conjunto independente?

É NP-Completo.

CONCEITO:
Clique de um grafo é um subgrafo onde todos os vertices estão conectados a todos os outros vertices.

Note que ambos os problemas são equivalentes, pois a transposta do grafo para o qual se quer saber se existe o conjunto independente
só vai possuir um clique se o original possuir um conjunto independente, portanto pode-se mapear um para o outro.
Agora sera que a tranformação de pegar a transposta é polinomial?
Se sim isso prova que o clique é NP se o conjunto independente for NP.

É NP-Completo.