A Classe de Problemas NP
Referências:
• M. R. Garey and D. S. Johnson. Computers and Intractability: a Guide to the
Theory of NP Completeness. Freeman, 1979. (biblioteca da FEUP)
• Richard Karp. NP-Complete Problems. Tutorial em video, 1993. (biblioteca da
FEUP)
•David Harel. Algorithmics- The Spirit of Computing. Addison-Wesley 1987.
NP
Fácil e difícil
 situação "normal": tempo de execução linear no tamanho da entrada
-
a maior parte dos algoritmos vistos (excepto o do fluxo numa rede que é polinomial)
-
os casos em que se obtém melhor que linear envolvem pré-processamento ou são problemas
aritméticos
Mas há situações "estranhas", mesmo na Lógica:
S1: esta frase tem mais do que 10 caracteres – V
S2: esta frase está escrita em Inglês – F
S3: esta frase é verdadeira – V
S4: esta frase é falsa – F , V ?
S4 é INDECIDÍVEL
— problema está na auto-referência
NP
Fácil e difícil
 Problema da terminação
-
Algoritmo A
while( X != 1 ){ X= X-2 }
Stop
-
Termina para entradas X ímpar; não termina para entradas X par
-
Algoritmo B
while( X != 1 ){
if( X é par ){ X= X/2 }
else { X= 3*X+1 } }
Stop
-
Entrada 7 dá sequência 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 e termina
-
Todas as entradas em que foi testado conduziram a sequências que terminaram, por vezes
após crescerem muito e flutuarem de forma imprevisível. Mas não se conseguiu provar que
terminam sempre (problema da Teoria dos Números).
-
Parar quando?
NP
Fácil e difícil
 Problema da terminação — é possível construir um programa capaz de detectar
ciclos infinitos? (útil para compiladores...)
• programa LOOP(P), com parâmetro programa P, corre P sobre ele próprio, isto é, executa P(P);
- responde SIM se P entrar em ciclo; entra em ciclo se P terminar
• aplicando LOOP a si próprio: P=LOOP
- se P(P) termina então LOOP(P) tem que entrar em ciclo; mas assim LOOP(LOOP) tem
que entrar em ciclo e terminar ao mesmo tempo
- se P(P) entra em ciclo, então LOOP(P) termina: contradição
- programa LOOP não se pode construir
LOOP
P
LOOP
LOOP
LOOP(LOOP)
P(P)
S
Termina?
N
S
Termina?
N
Contradição!
SIM
SIM
NP
Fácil e difícil
Circuito de Euler
(caminho que toca todas as arestas 1e 1 só vez)
Caminho mais curto a partir de um vértice
6
10
7
1
ALGORITMO LINEAR
2
5
4
Ciclo Hamiltoniano
(ciclo simples que passe em todos os vértices)
Caminho mais longo a partir de um vértice
ALGORITMO EXPONENCIAL
9
3
8
• Não tem caminho de Euler
• Não tem ciclo Hamiltoniano
NP
Fácil e difícil
Árvore de Steiner
- Qualquer par de pontos pode ser ligado por um segmento
- Problema: encontrar o mínimo da soma dos segmentos que ligam todos os pontos
obrigatórios (pontos opcionais podem ser usados também)
DIFÍCIL: ALGORITMO EXPONENCIAL
Mesma árvore sem pontos opcionais
FÁCIL: ALGORITMO LINEAR
n
5
10
20
30
n^3
125
1 000
8 000
27 000
2^n
32
1024
1 048 576
1 073 741 824
Uso do ponto opcional:
menor distância na ligação
dos 3 pontos
NP
Problemas de Pesquisa Combinatória
 De uma estrutura vasta de soluções possíveis, escolher uma que satisfaça
determinadas restrições
 Variantes
•
•
Problemas de decisão
Problemas de optimização
 Exemplos
•
•
•
•
•
Escalonamento: de operações de manufactura, de voos, de aulas
Encaminhamento: veículos, chamadas telefónicas, bits, petróleo, gás
Planeamento: de equipamentos numa cidade, de componentes numa placa
de VLSI
Biologia Computacional
Criptografia
NP
Tratabilidade
• Definição informal (J. Edmonds, 1965)
– Um problema é tratável se pode ser resolvido num número de passos
limitado por uma função polinomial no tamanho da entrada
• Requer formalização de
– Problema
• reduz-se a problema de decisão
• procurar valor mínimo de função  provar que existe valor < k
– Entrada
• codifica-se em cadeia de 0’s e 1’s, tamanho é nº de bits
– Resolver problema
• aceitar ou rejeitar uma entrada (decisão)
– Número de passos
• usa-se modelo de computação universal (máquina de Turing)
P: conjunto de problemas de decisão solúveis em tempo polinomial
NP
Tratabilidade
• Porquê “tratável” para problemas polinomiais?
– (N100) não parece muito tratável...
• Problemas polinomiais típicos: ordem baixa
• Paralelização
– pode ser usada para aumentar poder de cálculo
– pode compensar a ordem de crescimento
• Polinómios têm boas características de fecho
– fechados sob operações de adição, multiplicação, composição
– Ex: saída de algoritmo polinomial é entrada de outro algoritmo
polinomial : algoritmo resultante é polinomial
NP
Problemas de Decisão
• Problemas de Optimização
– têm objectivos muito diversos
– é difícil uniformizar problemas e soluções
• Problemas de Decisão
– Soluções são respostas Sim/Não
– Exemplo: Problema do caminho mais curto
• Optimização: encontrar o caminho mais curto
• Decisão: Sim/Não existe um caminho de comprimento <k
• Como comparar soluções
– Problema de optimização fácil - problema de decisão fácil
– Problema de decisão difícil- problema de optimização difícil
NP
Problemas em P
• Um problema L é da classe P se existe um algoritmo A tal que
– A aceita todas as entradas de L
– A rejeita todas as entradas que não são de L
– Há um polinómio f tal que, para qualquer entrada x, A termina antes de
f(|x|) passos
• Redução em tempo polinomial
– Um problema de decisão L é redutível a um problema de decisão M se
existe uma função polinomial computável F de strings em strings tal que
x é aceite por L se e só se F(x) é aceite por M
– Nestas condições, diz-se que M é pelo menos tão geral como L (pelo
menos tão difícil como L)
x
F
F(x)
M
Se L é redutível a M,
e M está em P,
então L está em P também
NP
Problema da satisfação Booleana
–
–
–
–
Variáveis proposicionais: A, B, C, …
Literais: A, ~A, B, ~B, …
Cláusulas: A  ~B  ~D  ~F
Forma Normal Conjuntiva (CNF): conjunção de cláusulas
(A  ~B  ~D  ~F)  (C  B  ~D)  (~A  F  D)  ...
• Fórmula CNF é satisfazível se
– existe uma atribuição de valores lógicos às variáveis que
torna a fórmula verdadeira
• Exemplo:
(A  ~B  ~D  ~F)  (C  B  ~D)  (~A  F  D)
atribuindo o valor V às variáveis A, B, F
e o valor F às variáveis C, D a fórmula é verdadeira.
NP
Problema dos vértices com 3 cores
Colorir os nós de um grafo de forma
a que nenhum par de nós adjacentes
fique com a mesma cor
Redução de 3 cores a satisfação Booleana:
Variáveis para cada vértice: Ri Gi Bi
Cláusulas
Para cada vértice:
Ri  Gi  Bi
~ Ri  ~Gi
~ Ri  ~Bi
~ Gi  ~Bi
Para cada aresta:
~ Ri  ~Rj
~ Bi  ~Bj
~ Gi  ~Gj
Satisfação Booleana é pelo menos tão geral (tão difícil) como 3 cores
NP
Classe NP
 Classe NP (algoritmo não determinístico de verificação polinomial)
• classe de problemas de decisão que podem ser verificados em tempo
polinomial
(intuição: solução pode ser difícil de encontrar, mas é fácil verificar que satisfaz o problema)
•
•
máquina não determinística tem uma escolha de passos seguintes e faz
sempre a escolha óptima (adivinha!) — característica poderosa mas
limitada: não serve para resolver problemas indecidíveis
descoberta uma solução, a sua verificação é polinomial
Ex: dado um ciclo Hamiltoniano é fácil confirmar
 Formalmente (R. Karp):
•
Um problema de decisão L está em NP se e só se existe um algoritmo de
decisão polinomial A tal que x está em L se e só se existe uma testemunha
y, de tamanho limitado por um polinómio no comprimento de x, tal que A
aceita o par (x, y)
NP
Problemas NP-completos
Um problema é NP-completo se qualquer problema em NP
puder ser reduzido àquele em tempo polinomial
 São os mais difíceis da classe; podem ser usados como subrotinas para a solução
dos outros (reduz-se problema P1 a problema P2 que é NP-completo, resolve-se
este e reconverte-se a solução)
 Se se descobrir uma solução polinomial para um deles, fica descoberta para
todos, pois a conversão é polinomial
 Suponhamos P1 NP-completo e P2 em NP; além disso existe uma redução
polinomial de P1 a P2; como qualquer problema em NP se reduz
polinomialmente a P1, também se reduz a P2; então P2 é NP-completo
 Teorema de Cook (1971): Satisfação Booleana é NP-completo
 Prova: problemas de NP podem ser resolvidos em tempo polinomial por uma
máquina não determinística; funcionamento desta pode ser descrito por uma
expressão Booleana; obter resposta para um problema reduz-se a satisfazer a
expressão.
NP
Ciclo Hamiltoniano  Caixeiro Viajante
 Problema do caixeiro-viajante:
Dado um grafo completo com custos nas arestas e um inteiro K existe um ciclo
simples que visite todos os vértices e tenha um custo total  K?
- aplicação: posicionamento de um furador de circuitos impressos para encaixar
componentes (deslocar é que demora, não é furar)
 Assumindo que o problema do ciclo Hamiltoniano é já sabido ser NP-completo
 reduz-se ciclo Hamiltoniano ao do caixeiro viajante:
 um grafo G é convertido num grafo completo G' com os mesmos vértices
 aresta de G’ tem peso 1 se pertencer a G e 2 caso contrário
 K igual ao número de vértices
 G tem um ciclo Hamiltoniano sse G' tiver um percurso de caixeiro viajante de
custo total K
NP
Satisfação Booleana  Cobertura de Vértices
 Problema da cobertura de vértices (VC):
Dado um grafo, decidir se as suas arestas podem ser cobertas por um número K
de vértices; cada aresta tem de ser incidente com pelo menos 1 dos K vértices
 Solução sobre um grafo G: subconjunto  dos vértices
- cada aresta de G tem um dos vértices em 
-  tem K ou menos elementos
 Problema é NP – a decisão sobre uma solução é feita em tempo polinomial
 Para mostrar que VC é NP-completo: reduz-se SAT a VC
Variáveis de SAT: X1, X2, ...Xn
Cada variável Xi: 2 vértices ui e vi e uma aresta (ui, vi)
Cada cláusula Ci= L1  L2  L3  ... Lm: 1 grafo completo com m vértices wi1, ...wim
Ligação entre vértices:
Se Lj = Xk
ligar wij a uk
Se Lj = ~Xk
ligar wij a vk
Inteiro K do problema VC: nº variáveis + nº ocorrências de literais - nº de cláusulas em SAT
NP
Satisfação Booleana  Cobertura de Vértices
 Exemplo de expressão de SAT
(X1  X2  ~X3)  (~ X1  X3)  (X1  ~ X2  X3)  (X2)
U1
w11
V1
U2
V2
U3
V3
w12
w21
w13
w22
w32
w31
w41
w33
NP
Solução de SAT é solução de VC
• S tem resposta SIM em SAT
– existe atribuição de valores lógicos a variáveis que satisfaz as cláusulas
• No problema VC correspondente, fazer uma cobertura V :
– cada variável com valor V: Ui está em V
– cada variável com valor F: Vi está em V
– cada cláusula: pelo menos 1 literal é V, logo o nó w correspondente é
adjacente a um vértice de V
– todos os outros vértices w: vão para V
• Cobertura V tem número de vértices não superior a K
– V tem exactamente K vértices
• Então V tem uma resposta SIM em VC
NP
Solução de VC é solução de SAT
• Problema V tem resposta SIM em VC
– grafo construído de acordo com a transformação dada tem cobertura com
não mais de K vértices
• cada subgrafo (Ui, Vi) precisa de 1 vértice na cobertura
• cada subgrafo completo wi1, wi2, ..., win tem no máximo 1 vértice que não
está na cobertura (se retirarmos mais do que 1, alguma aresta fica descoberta)
• Instância correspondente de SAT (S)
– Para cada Ui em V , fazer Xi = V
– Para cada Vi em V , fazer Xi = F
– Cada subgrafo completo tem um vértice wi que não está em V .
• por construção do grafo, o vértice wi é adjacente a um de Ui ou Vi, seja W
• como V é cobertura, W tem de estar em V ou wi não estaria coberto
• Então S, o problema SAT original, também tem resposta SIM
– cada cláusula tem 1 literal com valor V
NP
P=NP ?
 Mais importante problema em aberto na Ciência da Computação
 Se L é NP-completo: L está em P se e só se P = NP
 Não se conseguiu ainda encontrar nenhum problema NP que se prove não ter
solução polinomial
- é muito difícil provar limites inferiores exponenciais
portanto o não-determinismo pode não ser um avanço importante!
 Nem todos os problemas decidíveis estão em NP
• determinar se um grafo não possui ciclos Hamiltonianos — enumerar
todos os ciclos? Não se sabe se está em NP.
Decidível
NP
?
P
NP
Conclusão
 Problema NP-completo: não devemos esperar encontrar algoritmo eficiente
para resolvê-lo em todos os casos
 Alternativa:
Procurar algoritmos que lidem com a maior parte das instâncias do problema
Em problemas de optimização: aceitar soluções aproximadas (subóptimas)
Referências:
• M. R. Garey and D. S. Johnson. Computers and Intractability: a Guide to the
Theory of NP Completeness. Freeman, 1979.
• Richard Karp. NP-Complete Problems. Tutorial em video, 1993. (biblioteca da
FEUP)
•David Harel. Algorithmics- The Spirit of Computing. Addison-Wesley 1987.
NP