AEDs III 01/06/2011

A professora começou hoje corrigindo um problema que ela apresentou na ultima aula.
não sei se eu anotei esse problema na ultima aula mas vou apresenta-lo novamente aqui:

Prove que o problema do Clique é NP-Completo
sabendo que conjunto de NPC é ao menos: {circuit-SAT, SAT, 3-CNF SAT}
// Nota: o SAT é akele problema de satisfação de uma equação booleana.
//       O Circuit SAT parece que é mais complicado e tem haver com um boolean em circuito, nem sei como funciona.
//       O 3-CNF SAT é um sat onde a eq. booleana é da forma (x1+x2+x3)(x4+x5+x6) (3 elementos) . ..  etc
//       Ou seja um and de quantas entradas quanto se desejar onde cada entrada corresponde a um OR de 3 variáveis.

O problema é de 3 partes:

Mostre que clique é NP.
Para isso basta encontrar um algoritimo ñ deterministico para resolver ou mostrar que a verificação de uma amostra é polinomial.

Mostre uma tranformação polinomial da entrada de um dos 3 SATs para o clique.

Mostre que se houver um conjunto clique para essa entrada tranformada há uma satisfação para o problema do SAT que gerou a entrada.
E mostre que Se há uma solução para o SAT que gerou a entrada, há um clique para a entrada transformada.

A parte 1 vou desconsiderar, pois é mais simplizinha

// (entenda clausula como o conjunto booleano entre parenteses (x1+x2+x3))
A parte 2 é um algoritimo que gera um vertice para cada booleano de cada clausula do 3-CNF SAT
e coloca uma transição entre 2 vertices se for possível que ambos os booleans que os representam possam ser validos simuntaneamente.
Mas não deve haver nenhuma transição entre vertices da mesma clausula.

E o número k do clique deve ser igual ao número 3 do 3CNF SAT.

Agora provar a ida e a volta de que se há um clique de tamanho no minimo 3 há uma solução para o SAT gerador, e vice-versa.

// A professora mostrou esta resolução no quadro e desenhou um grafo para o 3CNF SAT: (x1+x2+x3)(x1_+x2+x3_)(x1+x2+x4)
// sendo o _ após alguns dos booleanos a notação de "complemento" ou "not"

// E da pra ver fácil que se x1 x2 e x4 podem ser validos ao mesmo tempo, então vai ser formado um triangulo de ligações entre os 3
// e se voce pensar bem um triangulo é um conjunto clique de 3 posições e portanto a existencia desse triangulo
// garante a existencia de uma satisfação para o SAT, e mostrou o contrario também, mas não vou escrever isso aqui.

// O ponto desse problema é mostrar passo a passo o processo de imaginar uma solução para esse problema, ficar mastigando
// as possibilidades e etc, o que é bem cansativo e as vezes parece que nem tem jeito de fazer.
// Bem não é um bom exemplo para se estudar em um texto porque devia ser uma aula participativa, mas fazer o que. . .

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *