Análise e Técnicas de Algoritmos
Período 2003.1

NP-Completude

Introdução

• Existem alguns problemas computacionais que são difíceis de serem resolvidos.
• Impossível de se provar que não existe solução eficiente.
• Como definir a eficiência de uma solução?
  • Vimos em nosso curso a conveniência de se utilizar medidas de complexidade como medida de eficiência.
  • Que conclusões tirar da tabela abaixo?

Funções de Complexidade	Tamanho da Entrada $n$
	10	20	30	40	50	60
$n$	.00001 seg	.00002 seg	.00003 seg	.00004 seg	.00005 seg	.00006 seg
$n^2$	.0001 seg	.0004 seg	.0009 seg	.0016 seg	.0025 seg	.0036 seg
$n^3$	.001 seg	.008 seg	.027 seg	.064 seg	.125 seg	.216 seg
$n^5$	.1 seg	3.2 seg	24.3 seg	1.7 min	5.2 min	13.0 min
$2^n$	.001 seg	1.0 seg	17.9 min	12.7 dias	35.7 anos	366 sec.
$3^n$	.059 seg	58 min	6.5 anos	3855 sec.	$2x10^8$ sec.	$1.3x10^13$ sec.

• Um algoritmo é eficiente quando a sua complexidade for polinomial em relação ao tamanho de sua entrada.
  • Um algoritmo é dito ser de tempo poliniomial se for $O(n^k)$, para alguma constate $k > 0$.
  • Qualquer outro algoritmo que não for polinomial é dito ser exponencial.
  • Classificação não é absoluta.
  • Algumas vezes pode ser insatisfatória mas, na maioria dos casos, é aceitável.
• Essa definição de eficiência nos dá noção sobre intratabilidade de problemas.
  • Um problema é dito tratável se ele apresenta uma solução polinomial.
  • Um problema é intratável se ele for tão difícil que nenhum algoritmo polinomial pode resolvê-lo.
  • Alguns algoritmos polinomiais podem não ser muito úteis. Por exemplo, se for $O(n^{100}$. Na prática, porém, quase sempre os polinômios são de grau 2 ou 3.
  • Alguns problemas são tão difíceis que são indecidíveis. Por exemplo, o problema da parada.
  • Por outro lado, alguns problemas são decidíveis mas, intratáveis.
• Vamos estudar certos problemas que são, de fato, difíceis (computacionalmente) de se resolver.
• Esse é a idéia central da teoria de NP-Completude.
• Vamos mostrar que encontrar uma solução eficiente para um certo problema é tão difícil quanto encontrar soluções eficientes para todos os problemas definidos em uma classe de problemas que chamamos NP.

Problemas de Decisão

• Um problema algorítmico é caracterizado por:
  • Conjunto de dados.
  • Objetivo do problema.
  • Solução.

Exemplo: Problema algorítmico

• Problema: Encontrar um clique de tamanho $\geq k$ num grafo $G$ dado.
• Conjunto de dados: Um grafo $G$ e um inteiro $k > 0$.
• Objetivo do problema: a própria descrição do problema.

Classes de Problemas

• Problemas de Decisão: Problemas em que a saída (solução) é SIM ou NÃO.
• Problemas de Localização: Determinar uma certa estrutura $S$ que satisfaça um conjunto de propriedades dadas.
• Problemas de Otimização: Problemas de localização em que as propriedades satisfazem critérios de otimização.

É possível relacionar problemas de otimização e localização com problemas de decisão. Por exemplo:

• Problema de Decisão:
  • Dados: Um grafo $G$ e um inteiro $k > 0$.
  • Objetivo: Verificar se $G$ possui um percurso de caixeiro viajante de peso $\leq k$.
• Problema de Localização:
  • Dados: Um grafo $G$ e um inteiro $k > 0$.
  • Objetivo: Localizar, em $G$, um percurso de caixeiro viajante de peso $\leq k$.
• Problema de Otimização:
  • Dados: Um grafo $G$.
  • Objetivo: Localizar, em $G$, um percurso de caixeiro viajante ótimo.

Todos os problemas que vamos utilizar no estudo de NP-Completude são problemas de decisão. Apesar de serem mais simples, já vimos que é possível relacionar um problema de decisão com problemas de localização e otimização. Prova de intratabilidade de problemas de decisão pode ser estendida aos outros casos.

Classes de Complexidade P e NP

• A Classe de Complexidade P é o conjunto de todos os problemas de decisão que são resolvíveis em tempo polinomial em um computador determinístico.
• A Classe de Problemas NP é o conjunto de problemas resolvíveis em tempo polinomial em um computador não-determinístico. A Classe NP também pode ser definida como a classe de problemas em que é possível verificar em tempo polinomial, se um determinada solução proposta satisfaz o problema de decisão.
• O complemento $\overline{D}$ de um problema de decisão $D$ é um problema de decisão cujo objetivo é o complemento da decisão de $D$.
• A Classe Co-NP compreende exatamente os complementos dos problemas da classe NP.
• Relação entre as classes P e NP:
  • É fácil verificar que $P \subset NP$.
  • $P = NP$ ou $P \neq NP$? Até o momento não se conhece uma resposta para essa pergunta. Todas as evidências apontam na direção de $P \neq NP$ mas, nenhuma prova foi apresentada para esse problema. Essa resposta vale U$1 milhão (ver em http://www.claymath.org/prizeproblems/index.htm).
  • Se $P \neq NP$, $NP - P$ são problemas intratáveis.
  • Outras conjecturas: $NP \neq Co-NP$ e $P \neq NP \cap Co-NP$.

Alguns Problemas de Decisão em NP

Problema 1: Satisfabilidade

O problema da satisfabilidade (SAT) é um problema de lógica que envolve expressões booleanas. Pode ser definido da seguinte forma:

• Dados: Uma expressão booleana $E$ na sua forma normal conjuntiva (FNC).
• Objetivo: Verificar se $E$ é satisfatível, ou seja, verificar se existe uma atribuição de valores às variáveis da expressão de tal modo que a expressão seja avaliada verdadeira.

Uma expressão é FNC quando for uma conjunção de cláusulas. Por exemplo, $(x_2 \vee \overline{x_1}) \wedge (\overline{x_1} \vee \overline{x_3} \vee x_2) \wedge (x_3) \wedge (x_1 \vee \overline{x_3} \vee x_2)$.

Problema 2: Conjunto Independente de Vértices

• Dados: Um grafo $G$ e um inteiro $k > 0$.
• Objetivo: Verificar se $G$ possui um conjunto independente de vértices de tamanho $\geq k$.

Dado um grafo $G = (V, E)$, um conjunto independente de vértices é um subconjunto $V_1 \subset V$ tal que qualquer par de vértices de $V_1$ não é adjacente. Por exemplo, na figura abaixo: $V_1 = \{ a, c, b, g, h \}$ é um conjunto independente de vértices de tamanho 5.

Problema 3: Clique

• Dados: Um grafo $G$ e um inteiro $k > 0$.
• Objetivo: Verificar se $G$ possui um clique de tamanho $\geq k$.

Dado um grafo $G = (V, E)$, um clique é um subconjunto $V_1 \subset V$ tal que qualquer par de vértices de $V_1$ é adjacente. Por exemplo, na figura acima: $V_1 = \{ d, b, e \}$ é um clique de tamanho 3.

Problema 4: Cobertura de Vértices

• Dados: Um grafo $G$ e um inteiro $k > 0$.
• Objetivo: Verificar se $G$ possui uma cobertura de vértices de tamanho $\leq k$.

Dado um grafo $G = (V, E)$, uma cobertura de vértices é um subconjunto $V_1 \subset V$ tal que qualquer aresta de vértices de $V$ é incidente a um vértice de $V_1$. Por exemplo, no grafo acima: $V_1 = \{ d, f, e \}$ é uma cobertura de vértices de tamanho 3.

Problema 5: Coloração

• Dados: Um grafo $G$ e um inteiro $k > 0$.
• Objetivo: Verificar se $G$ possui uma coloração com um número $\leq k$ de cores.

Dado um grafo $G = (V, E)$, uma coloração é uma atribuição de cores aos vértices do grafo, de modo que dois vértices adjacentes tenham cores distintas.

Problemas NP-Completos

• A classe de problemas NP captura o conjunto de problemas que acreditamos que sejam difíceis de se tratar.
• Existem, entretanto, problemas que podem ser considerados pelo menos tão difíceis como qualquer outro em NP.
• Essa classe de problemas mais difíceis em NP é chamada de NP-Completo ou NPC.
• O mundo NP pode ser visto como:

  

• No estudo de problemas NPC, faz-se necessário o conceito de redução de problemas.

Redução em Tempo Polinomial

• UMa redução polinomial de um problema de decisão $D_1$ em um problema de decisão $D_2$ é uma função $f: D_1 \rightarrow D_2$, em que:
  1. $f$ pode ser computada em tempo polinomial, e
  2. para toda instância $I$ de $D_1$, a resposta é a mesma se considerarmos a instância $I$ de $D_2$.

• A figura a seguir ilustra a definição de redução:

  

• $D_1 \stackrel{R}{\Rightarrow} D_2$ ou $D_1 \preceq _R D_2$.
• $D_2$ engloba $D_1$ já que pode representar um problema como $D_1$.
• Podemos concluir que $D_2$ é tão difícil quanto $D_1$. Se conhecermos um algoritmo para resolver $D_2$, temos um algoritmo para resolver $D_1$.
• Exemplo
  • $D_1:$ contar as cidades do estado.
  • $D_2:$ Caixeiro viajante.

Teorema de Cook

• SAT é NP-Completo.
• SAT tem a propriedade que todos os problemas em NP podem ser reduzidos a ele, em tempo polinomial.
• Existem outros problems em NP que têm as mesmas características de SAT.
• Se $D_1 \in NPC$ e $D_2 \in NPC$, então $D_1 \preceq _R D_2$ e $D_2 \preceq _R D_1$.
• É possível concluir:
  • Se um problema NPC pode ser resolvido em tempo polinomial, então todos os problemas de $NP$ podem sê-lo.
  • Se um problema de NP é intratável, todos os problemas de NPC são intratáveis.

Como Determinar se um Problema é NPC

Se $D_1, D_2 \in NP$, $D_1$ é NPC e $D_1 \preceq _R D_2$, então $D_2$ é NP-Completo.

Para provar se um problema de decisão $D$ é NP-Completo, devemos seguir os seguintes passos:

1. Mostra que $D \in NP$.
2. Selecionar, $D_1$, um problema NPC conhecido.
3. Achar uma redução de $D_1$ para $D$.
4. Mostrar que a redução foi feita em tempo polinomial.

Exemplos de Problemas NPC

Vamos apresentar como utilizar redução para provar que alguns dos problemas conhecidos são NPC. A figura abaixo mostra um resumo dos problemas que vamos mostrar a prova. Cada arco denota uma redução em tempo polinomial.

3SAT

O problema 3SAT consiste em determinar o resultado de uma expressão booleana $E$ que está escrita em sua FNC é satisfatível. Cada cláusula de $E$ tem exatamente três literais. Por exemplo, $(\overline{v_1} \vee v_2 \vee \overline{v_7}) \wedge (v_3 \vee \overline{v_5} \vee v_6) \wedge (v_1 \vee v_5 \vee \overline{v_8})$ é uma instância de 3SAT.

Aplicando os passos para determinar se 3SAT é NPC temos:

1. 3SAT é claramente NP.
2. SAT é NPC. Se SAT $\preceq _R$ 3SAT. (vamos mostrar como a redução é feita)
3. Se a redução é feita em tempo polinomial, 3SAT é NPC.

Para fazer a redução, devemos substituir cada cláusula $C_i$em $E$ por:

• Se $C_i = (a)$, devemos trocar por $S_i = (a \vee b \vee c) \wedge (a \vee \overline{b} \vee c) \wedge (a \vee b \vee \overline{c}) \wedge (a \vee \overline{b} \vee \overline{c})$.
• Se $C_i = (a \vee b)$, devemos trocar por $S_i = (a \vee b \vee c) \wedge (a \vee b \vee \overline{c})$.
• Se $C_i = (a \vee b \vee c)$, não fazemos nada.
• Se $C_i = (a_1 \vee a_2 \vee ... a_k ), k>3$, devemos trocar por $S_i = (a_1 \vee a_2 \vee b_1) \wedge (\overline{b_1} \vee a_3 \vee b_2) \wedge... ...a_4 \vee b_3) \wedge ... \wedge (\overline{b_{k - 3}} \vee a_{k - 1} \vee a_k)$.
• As variáveis adicionadas são novas variáveis que não estão sendo usadas.

Cobertura de Vértices

Vamos reduzir o problema 3SAT ao problema de cobertura de vértices.

• Para cada variável $v_i$ usada na fórmula $S$, adicionamos dois vértices m $G$. Rotular um com $v_i$ e o outro com $\overline{v_i}$. Adicionar ainda um arco ligando $v_i$ a $\overline{v_i}$.
• Para cada cláusula $C_i = (a \vee b \vee c)$ em $S$, formar um triângulo consistindo de três vértices $i_1$, $i_2$ e $i_3$. Adicionar arcos $(i_1, i_2)$, $(i_2, i_3)$ e $(_3, i_1)$.
• Para cada cláusula $C_i = (a \vee b \vee c)$, adicionar as arestas $(i_1, a)$, $(i_2, b)$ e $(i_3, c)$.
• Fazer $k = n + 2m$, em que $n$ é o número de variáveis de $S$ e $m$ é o número de cláusulas.