MÓDULO 6 - COMPLEXIDADE COMPUTACIONAL - PARTE I

Prévia do material em texto

1 
 
Módulo 6 - Comlpexidade Computacional – A Classe P e a Classe NP – 
Grafos Eulerianos e Hamiltonianos 
 
Uma Linguagem L é denominada polinomialmente decidível se existe uma 
Máquina de Turing determinística polinomial que a decide. 
Uma Máquina de Turing (MT) é denominada polinomial se a máquina sempre 
para, qualquer que seja a entrada x de comprimento n, após p(n) transições, onde p(n) 
é uma função polinomial do comprimento n da cadeia de entrada. 
Todo algoritmo prático/eficiente pode ser reduzido a uma Máquina de Turing 
limitada em tempo polinomial. 
São exemplos de algoritmos polinomiais: caminho de Euler, o problema da 
Satisfabilidade Booleana SAT 2 e o problema da Alcançabilidade. 
 
Caminho de Euler 
Definição do problema: Dado um grafo G, existe algum caminho em G que use 
todas as arestas exatamente uma vez? 
Teorema: existe um Caminho de Euler em um grafo conexo se, e somente se, não 
existem nós ímpares ou existem exatamente dois nós ímpares. 
A solução é polinomial. De fato, sua solução consiste em 
 Inspeciona-se a matriz de adjacência e calcula-se para cada linha i o 
grau do nó i, simplesmente, efetuando-se: grau = grau + A[i, j]. 
 Ao final, verifica-se se o grau daquele nó (linha) é ímpar. Se for, 
incrementa-se o total de nós ímpares. 
 Naturalmente, se o total (de nós ímpares) for 0 ou 2, então existe o 
Caminho de Euler. 
 Em uma matriz n  n, devem ser inspecionadas n linhas. 
 
Naturalmente, o algoritmo é O(n2) no pior caso. 
 
Satisfabilidade Booleana 
 Uma fórmula booleana é composta por variáveis e operações 
booleanas. 
 Literal é a variável booleana ou variável booleana negada. 
 Cláusula: fórmula booleana composta por literais e a operação “OU”. 
 Fórmula normal conjuntiva: composta por cláusulas conectadas pelo 
operador “E”. 
 
2 
 
 2SAT: instâncias do problema da satisfabilidade booleana 
apresentam 2 ou menos literais em cada cláusula, na sua forma 
normal conjuntiva. 
 
Exemplo: Seja a fórmula normal conjuntiva: 
 
O problema da satisfabilidade-2 pertence à classe P. 
Exemplo de solução: 
 Atribui-se um valor “True” para a primeira literal da primeira cláusula; 
 nas cláusulas que se sucedem, sempre que ocorrer esta literal, o 
valor recém-atribuído é substituído; 
 após O(n) etapas, em que n é o número de cláusulas, a 
satisfabilidade é decidida. 
 
Alcançabilidade 
 Linguagens codificam problemas. Um problema é um conjunto de entradas, 
tipicamente infinito e uma questão do tipo sim/não arguida para cada entrada 
(propriedade que a entradapode ter ou não). 
 Problema da alcançabilidade: dado um grafo direcionado G  V  V, em que V 
= {v1, v2, ...,vn} é um conjunto finito, e dois vértices vi, vj V, existe um caminho 
vi para vj em G? 
 Trata-se de um problema com solução com desempenho O(n3). 
 
Circuito Hamiltoniano 
 Dado um grafo G, existe um circuito que passe por todos os nós de G 
exatamente uma vez. 
 O único algoritmo conhecido para este problema consiste em examinar todas 
as permutações possíveis dos nós e, para cada permutação, verificar se se 
trata de um circuito hamiltoniano. 
 Trata-se, portanto, de um problema O(n!). 
 
Definição da classe P: P é a coleção de todos os conjuntos reconhecíveis por 
Máquinas de Turing determinísticas em tempo polinomial. 
Definição da classe NP: NP é a coleção de todos os conjuntos reconhecíveis por 
máquinas de Turing não determinísticas em tempo polinomial. 
 
 
3 
 
Exercício Resolvido 1: 
Considere o grafo G = (V, A, g), em que: 
V = {1, 2, 3, 4, 5} são os vértices 
A = {a, b, c, d, e} 
g(a) = 1‑2 
g(b) = 2 – 5 
g(c) = 1 – 3 
g(d) = 5‑ 5 
g(e) = 3‑4 
Pede‑se: verificar se existe um caminho de Euler 
 
Resposta: A matriz de adjacência de G é dada por: 
M =
0
0
1
1
0
1
0
0
0
1
0
1
0
0
1
1
0
1
0
0
0
1
0
1
0
 
Assim identifica‑se que grau(1) = grau(2) = grau(3) =grau(4) = grau(5) = 2 
Portanto, o número de nós ímpares é 0. Assim sendo, pelo Teorema de Euler, existe 
um caminho que passa por todas as arestas. Como o número de nós ímpares é 0, o 
caminho pode se iniciar em qualquer nó. 
O caminho pode ser: 1a2b5d4e3c1. 
Exercício Resolvido 2: Considere o grafo G = (V, A, g), em que: 
V = {1, 2, 3, 4, 5, 6, 7, 8} são os vértices 
A = {a, b, c, d, e} 
g(a) = 2‑6 
g(b) = 4‑3 
g(c) = 2 – 3 
g(d) = 1‑4 
g(e) = 1‑2 
g(f) = 5‑6 
g(g) = 5‑ 8 
g(h)=8‑7 
g(i)= 6‑7 
g(j) = 7‑3 
g(k) = 8‑4 
Pede‑se: verificar se existe um ciclo Hamiltoniano. 
Resposta: O algoritmo para este problema consiste em identificar as 8! permutações 
dos nós e verificar se, uma ou mais, constituem um ciclo hamiltoniano. Por outro lado, 
por tentativa e erro é possível se constatar que este grafo apresenta o seguinte ciclo: 
6i7j3c2e1d4k8g5f6 
 
4 
 
Referências 
Gersting, J. L. Fundamentos Matemáticos para a Ciência da Computação Rio de 
Janeiro: LTC, 2001. 
Lewis H. R. ; Papadimitrious, C. H. Elementos da Teoria da Computação Porto Alegre: 
Bookman, 2004.