Classes de Complexidade e o Problema Partition

Prévia do material em texto

Universidade Federal de São Paulo ­ UNIFESP 
Instituto de Ciência e Tecnologia 
 
 
 
Linguagens Formais e Autômatos 
 
 
 
Problemas Intratáveis 
 
 
 
 
Natália de Faria 
Salety Ferreira Baracho 
 
 
Apresenta­se neste trabalho a classe de           
problemas P e NP e o problema             
NP­Completo Partition como     
cumprimento de umas das atividades da           
disciplina Linguagens Formais e       
Autômatos ministrada pelo Prof Dr         
Antonio Augusto Chaves.  
 
 
 
 
 
 
 
 
São José dos Campos, Junho de 2014. 
 
1 
SUMÁRIO 
 
1 Introdução …………………………………………………………………………………   03 
2 Classes de Complexidade …………………………………………..………….….……   03 
2.1 Classe de complexidade P e NP …………………………………………...…  03 
2.2 Classe de complexidade NP­Completo ………………………………………  05 
3 Problema Partition …………………………………………………………………..……   06 
3.1 O problema …………………………………………………………………...…  06 
3.2 A Prova ……………………………………………………………………….….  06 
Prova 1: a partir de Subset­Sum …………………………………………..…   07 
Prova 2: a partir de Knapsack ………………………………………………..   07 
3.3 Outras Soluções ……………………………………………………………….   08 
3.3.1 ­ Algoritmo de tempo Pseudo­Polinomial ……………………………..   08 
3.3.2 ­ Algoritmo de abordagem por aproximação ………………………….   09 
3.3.3 ­ Outras abordagens …………………………………………………….   10 
4 Referencias ……………………………………………………………………………….   11 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2 
 
1 Introdução 
 
A mera existência de um programa de computador capaz de resolver um problema não                           
significa que sua solução por meios computacionais seja de fato viável. Pois para muitos                           
problemas importantes ainda não é possível encontrar soluções mais elegantes que a busca                         
exaustiva. O principal problema da busca exaustiva é que sua implementação requer um                         
número de passos computacionais proporcional ao número de possibilidades no espaço de                       
busca, o que é em geral uma função de crescimento exponencial no tamanho das instâncias do 
problema. Com a descoberta de novos algoritmos, ficou claro que a existência de um algoritmo                             
de complexidade exponencial para um problema não significava que a complexidade real do                         
problema era exponencial. [10] 
Existem várias classes de complexidade. Para classificar um problema de acordo com                       
a sua complexidade é preciso relacionar fatores como limitação de recurso, modelo                       
computacional e tipo de problema. Porém interessa­nos aqui apenas as classes de problemas                         
P, NP e NP­Completo. Sendo assim, apresenta­se neste relatório a definição de cada uma                           
dessas classes e a prova por redução de que o Problema Partition é um problema                             
NP­Completo. 
 
2 Classes de Complexidade 
 
Uma classe de complexidade representa um conjunto de problemas de complexidade                     
relacionados que podem ser classificados com base em três fatores: 
 
● Limitação de recursos: tempo, espaço, etc; 
● Modelo computacional: Maquina de Turing deterministica não deterministica ou                 
quantica, circuitos booleanos, circuitos monótonos, etc; 
● Tipo de problema: de decisão, de função, de otimização, de contagem, etc. 
 
2.1 Classe de complexidade P e NP 
 
3 
Resumidamente, P representa a classe de problemas com soluções que podem ser                       
encontradas de modo eficiente e NP representa a classe de problemas com soluções que                           
podem ser verificadas de modo eficiente. 
As classes P e NP de problemas que podem ser resolvidos em tempo polinomial por                             
TM’s determinísticas e não­determinísticas, respectivamente, e a técnica de redução de                     
polinomial tempo são, de acordo com Hopcroft [1], os conceitos básicos da teoria da                           
intratabilidade. 
Sendo assim, inicia­se o esclarecimento sobre os problemas que podem ser resolvidos                       
em tempo polinomial. Para tanto, uma máquina de Turing M é dita de complexidade de tempo                               
T(n) se, sempre que M recebe uma entrada w de comprimento n, M pára depois de efetuar no                                   
máximo T(n) movimentos, independente do fato de M aceitar ou não. Essa definição se aplica a                               
qualquer função T(n), como T(n) = 50n2 ou T(n) = 3n + 5n4; no entanto, importa­se o caso em                                     
que T(n) é um polinômio em n. Desta forma, uma linguagem L está na classe P se existe algum                                     
polinômio T(n) tal que L = L(M) para alguma TM determinística M de complexidade de tempo                               
T(n). 
Dentro deste contexto, uma classe fundamental de problemas no estudo da                     
intratabilidade é a dos problemas que podem ser resolvidos por uma TM não­determinística que                           
executa em tempo polinomial [1]. Formalmente, diz­se que uma linguagem L está na classe NP                             
(polinomial não­determinística) se existe uma TM não­determinística M e uma complexidade de                       
tempo polinomial T(n) tais que L = L(M) e, quando M recebe uma entrada de comprimento n,                                 
não existe nenhuma sequencia de mais de T(n) movimentos de M. 
Desta forma, como toda TM determinística é uma TM não­determinística que nunca tem                         
mais de uma opção de movimentos, P NP. Porém, parece que NP contém muitos problemas             ⊆                  
que não estão em P. Contudo, uma das mais profundas questões em aberto da matemática é                               
se P = NP, isto é, se de fato tudo que pode ser feito em tempo polinomial por uma NTM pode                                         
realmente ser feito por um DTM em tempo polinomial, talvez com um polinômio de grau mais                               
alto [1]. 
Até aqui, apresentou­se as definições que dão base para o entendimento dos problema                         
das classes P e NP. Entretanto, dado um problema, como provar que ele é um problema NP?                                 
Que metodologia utilizar? Para tanto, pode­se referenciar a metodologia de redução. 
Porquanto, seja P2 um problema que deseja­se provar ser NP, ou seja, um problema                           
que não pode ser resolvido em tempo polinomial e P1 que sabe­se não estar em P. Então,                                 
reduz­se P1 a P2. Exemplificando, suponha querer provar afirmação “se P2 está em P, então P1                               
4 
também está”. Tendo em vista a afirmação de que P1 não está em P, pode­se então afirmar                                 
que P2 também não está em P. 
 
2.2 Classe de complexidade NP­Completo 
 
Com uma certa entrada n pode­se decidir a saída com uma busca exaustiva, mas isto                             
pode tomar um tempo exponencial. No entanto, se é dado uma suposta saida é possível de se                                 
verificar a veracidade da afirmação em tempo polinomial. 
Desta forma, estes problemas não são apenas membros ordinários da classe NP. São                         
problemas NP de elite, designados NP­Completo. Isso quer dizer que se alguém descobrisse                         
um algoritmo de tempo polinomial para qualquer um dos problemas NP­Completo, este mesmo                         
algoritmo seria facilmente adaptado para todos os problemas NP em tempo polinomial. Cada                         
problema NP­Completo é um esqueleto para toda a classe NP [3]. 
Portanto, atualmente, todosos algoritmos utilizados para resolver problemas                 
NP­Completo tem tempo exponencial que varia de acordo com o tamanho da instância de                           
entrada. Então para resolver esses problemas em tempo hábil, aplica­se um ou mais dos                           
seguintes métodos: 
● Aproximação: dentro de um intervalo de erro conhecido encontra­se uma solução                     
não necessariamente ótima; 
● Probabilistico:A partir de uma análise dos conjuntos de entrada obtém­se uma                     
solução considerada boa em média; 
● Restrição: para obter­se algoritmos mais rápidos a quantidade de elementos da                     
entrada é restringida; 
● Parametrização: Para otimização dos algoritmos, fixa­se parâmetros de entrada; 
● Heurísticas: encontra­se algoritmos relativamente bons em tempos mais habeis,                 
porém não é possível provar a eficácia da solução ou sua rapidez. 
 
E para provar que um problema L é NP­Completo, no geral, utiliza­se a redução nos                             
seguintes passos [11]: 
 
1. Mostre que L é NP; 
2. Escolha uma linguagem B ∈ NPC de qual a redução virá, ou seja, B ≤p A. 
5 
3. Descreva a função de redução f. 
4. Suponha que se uma instância x ∈ B, então f(x) ∈ A. 
5. Suponha que se f(x) ∈ A, então x ∈ B. 
6. Brevemente explique porque f é computável em tempo polinomial. 
 
Normalmente omite­se o passo 1 quando é trivial [4]. 
 
3 Problema Partition 
3.1 O problema 
 
O problema Partition é a tarefa de decidir se um dado conjunto S de inteiros positivos                               
podem ser particionados em dois conjuntos S1 e S2 tais que a soma dos números em S1 seja                                   
igual a soma dos números em S2 [4]. 
Partition é um problema NP clássico. Com uma certa lista de n números a pergunta                             
“Esta lista possui uma partição perfeita?” pode ser respondida com uma busca exaustiva, mas                           
isto pode tomar um tempo exponencial. No entanto, se é dado uma suposta partição perfeita, é                               
possível de se verificar a afirmação em tempo polinomial. Sendo necessário apenas somar os                           
dois subconjuntos e comparar os resultados, que tomaria tempo proporcional a n [3,6]. 
Apesar do problema Partition ser do tipo NP­completo, existe uma solução de                       
programação dinâmica de tempo pseudo­polinomial, e existem heuristicas que solucionam o                     
problema em várias instâncias, tanto otimizadamente quanto aproximadamente. Por esta razão                     
ele é chamado “The Easiest Hard Problem” [3]. O problema Partition também é comumente                           
visto como um caso especial do problema Subset­Sum. 
 
3.2 A Prova 
 
Prova 1: a partir de Subset­Sum [4] 
Instância: <a1, a2, … , an> onde todos os ai são inteiros positivos apresentados em                             
binário. 
Condição de aceitação: Aceita­se existe S ⊆ {1, 2, …, n} tal que   .∑ 
i∈S
ai =   ∑
 
j∈S/
aj  
Teorema: Partition é NP­Completo 
Prova: É trivial notar que Partition é NP. 
6 
Provaremos que SubsetSum  ≤p Partition. 
Tome x uma entrada para SubsetSum. Assuma que x é uma instância de SubsetSum,                           
caso contrário poderia fixar f(x) uma string ∉ Partition. 
Então x = < a1, a2, … , am, t> onde t e todos os ai sao inteiros não negativos em binario. 
Seja a =  .  ∑
 
1≤i≤m
ai  
Caso 1: 2t ≥ a. 
Seja f(x) = <a1, a2, … , am, am+1>, onde am+1 = 2t­a. É perceptivel que f é computável em                                       
tempo polinomial. Desejamos mostrar que x ∈ SubsetSum ⇔ f(x) ∈ Partition. 
⇒  
Suponha que x ∈ SubsetSum. 
Seja S ⊆ {1, … , m} tal que t  ∑ 
i∈S
ai =    
Tomando T = {1, … , m} ­ S, temos que  .a  ∑
 
i∈T
ai =   − t  
Seja T’ = {1, … , m+1} ­ S, temos  .a ) a ) 2t )  ∑
 
i∈T ′
ai = ( − t + am+1 = ( − t + ( − a = t =   ∑
 
i∈T
ai  
Portanto f(x) ∈ Partition. 
⇐ 
Suponha f(x) ∈ Partition.  
Então ∃ S ⊆ {1, … , m+1} tal que T = {1, … , m+1} ­S 
Temos que  .  a 2t )]/2  ∑
 
i∈S
ai =   ∑
 
j∈T
aj = [ + ( − a = t  
Sem perda de generalidade, assuma que m+1 ∈ T.  
Então temos que S ⊆ {1, … , m}  e  .  ∑ 
i∈S
ai = T  
Portanto x ∈ SubsetSum. 
 
Caso 2: 2t ≤ a. Adiciona­se am+1 = a ­ 2t 
 
Prova 2: a partir de Knapsack [2] 
Corolário 1: Partition é NP­Completo 
Prova: Devemos transformar polinomialmente KnapSack para Partition. 
 
Dada qualquer instância c1,..., cn, K KnapSack, construimos a instância de Partition                       
c1,..., cn, cn+1 = 2M, cn+2 = 3M ­ 2K, onde M = K. Supomos que existe um subconjunto S                          ∑
n
j=1
cj >              
que está contido em {1, ..., n} com = K se, e somente se, existir um subconjunto S’ contido                ∑
 
j∈S
cj                      
em {1, ...,  n+2} tal que  ∑
 
j∈S′
cj =   ∑
 
j∈S/ ′
cj  
7 
Se, em qualquer partição viável S’ de {c1, …, cn+2}, cn+1 e cn+2 devem ficar separados,                               
pois somam 5M ­ 2K >  . Então temos, para S = S’ ­ {n+1, n+2},∑
n
j=1
cj  
.c c∑
 
j∈S
cj +   n+2 = ∑
 
j∈S, j=n+1,n+2/ /
cj +   n+1  
Segue aritmeticamente que = K, somente se supomos que para algum      ∑
 
j∈S, 
cj             ∑
 
j∈S, /
cj = K    
S ⊆ {1, 2, …, n}. Então segue que  .c c∑ 
j∈S
cj +   n+2 = ∑
 
j∈S/
cj +   n+1  
 
3.3 Outras Soluções 
 
Como dito anteriormente, é possível buscar soluções não necessariamente ótimas para 
o problema. Aqui apresenta­se dois algoritmos. 
3.3.1 ­ Algoritmo de tempo Pseudo­Polinomial 
Quando o tamanho da entrada e a soma dos elementos da entrada não for muito grande 
a ponto de estourar a limitação de memória pode­se utilizar programação dinâmica parar 
resolver o problema Partition [11]. 
Suponha que a entrada seja uma lista na forma S = x1, … , xn 
Seja N a soma de todos os elementos em S. Constroi­se um algoritmo que determina se 
existe um subconjunto tal que a soma seja [N/2]. Se existir tal subconjunto de S então: 
Se N é par, o resto de S também tem soma igual a [N/2]. 
Se N é ímpar, o resto de S também tem soma igual a [N/2]. 
Esta seria a melhor solução possível. 
 
Relação de recursividade 
Deseja­se determinar se existe um subconjunto de S tal que a soma de seus elementos                             
totalize [N/2]. Tome p(i, j): 
➢ verdadeiro, se um subconjunto de {x1, .. , xj} some i e falso caso contrário. 
Então p([N/2], n) é verdadeiro se, e somente se, existe um subconjunto de S tal que                               
sua soma seja [N/2]. O objetivo do algoritmo será computar p([N/2], n). Então tem­se a seguinte                               
relação recursiva 
➢ verdadeiro tanto se p(i, j­1) ou p(i­nj, j­1) for verdadeiro. 
➢ falso caso contrário. 
8 
A rasão para isso é que existe algum subconjunto de S tal que some i usando os                                 
números x1, … , xj e apenas se existir um subconjunto de x1, … , xj que: 
❖ não use xj e some i; 
❖ não use xj e some (i­xj), pois xj + (soma do subconjunto) = i. 
 
O algoritmo tem o objetivo de construir uma tabela de tamanho [N/2] x n contendo os                               
valores da recursão. Uma vez que a tabela esteja preenchida, retorna­se P([N/2], n).  
 
Entrada: Uma lista S de inteiros 
Saída: Verdadeiro se S pode ser particionado em dois subconjuntos de soma igual. 
1. função achar_partition(S): 
2. n ← |S| 
3. N ← soma(S) 
4. P ←  tabela booleana vazia de tamanho ([N/2] + 1) x (n + 1) 
5. inicializar linha superior (P(0,x)) de P com Verdadeiro 
6. inicializar a coluna mais a esquerda (P(x,0)) de P, exceto para P(0,0) com Falso 
7. para i de 1 até[N/2] 
8.      para j de 1 até n 
9.      P(i, j)  ←  P(i, j ­ 1) ou P(i ­ S[j­1], j ­ s) 
10. retornar P([N/2], n) 
Este algoritmo roda com tempo O(Nn), onde n é a quantidade de elementos na entrada e 
N é a soma dos elementos da entrada. 
 
3.3.2 ­ Algoritmo de abordagem por aproximação 
Uma abordagem para o problema é a imitação da forma como as crianças selecionam                           
os times para um jogo, o algoritmo greedy. 
Itera­se os números e ordena­os de forma decrescente, atribuindo­os um a um para o                           
subconjunto com a menor soma. Esta abordagem funciona bem quando os números da                         
entrada são do tamanho aproximado de sua cardinalidade ou menores. Este algoritmo roda em                           
tempo O(n log(n)). Esta abordagem é conhecida por dar uma aproximação de 4/3 da solução                             
ótima da versão otimizada, ou seja, se o algoritmo retorna dois grupos S1 e S2, então                               
max(soma(S1), soma(S2)) ≤ 4/3OTIMO. [7] 
 
1. função achar_partition(S) 
2. A ← { } 
9 
3. B ← { } 
4. rearranjar S em ordem decrescente 
5. para i em S: 
6.      se soma(A) ≤ soma(B) 
7.           conjunto A recebe i 
8.      senão 
9.           conjunto B recebe i 
10. retornar {A, B} 
 
3.3.3 ­ Outras abordagens 
Algoritmo da diferenciação 
Uma heuristica proposta por Narendra Karmarkar e Richard Karp [8] que a cada passo                           
remove dois números do conjunto e os substitui por sua diferença. Isso representa a decisão de                               
por dois números em dois conjuntos diferentes, sem decidir imediatamente qual número vai em                           
qual conjunto. 
Essa heurística tem uma performance melhor que a do algoritmo greedy, porém ainda                         
não é suficientemente boa para instâncias onde os números são exponenciais ao tamanho do                           
conjunto. 
Algoritmo de tempo qualquer 
Baseado na heuristica da diferenciação, que primeiro acha a solução retornada pela                       
mesma e então progressivamente acha soluções melhores de acordo com a disponibilidade de                         
tempo, podendo inclusive requerer tempo exponencial para otimização, nas piores instâncias                     
[9]. 
 
   
10 
4 Referencias 
 
1. Hopcroft, John E; Motwani, Rajeev; Ullman, Jeffrey D. Introdução à Teoria dos                       
autômatos, linguagens e computação. 2ed, Rio de Janeiro. Elsevier 2002. 
 
2. Papadimitriou, Christos H. Combinatorial optimization: algorithms and complexity.               
Englewood Cliffs, N. J. Prentice Hall 1982. 
 
3. Hayes, Brian (May–June 2002), "The Easiest Hard Problem", American Scientist                   
Disponível em:   
<http://www.americanscientist.org/issues/pub/2002/3/the­easiest­hard­problem>. 
Acesso em: junho de 2014. 
 
4. Kolokolova, Antonina (Fall 2007) (Memorial University). Disponível em:               
<http://www.cs.mun.ca/~kol/courses/6743­f07/lec10.pdf>. Acesso em: junho de 2014. 
 
5. Har­Peled, Sariel. (Spring 2005) (University of Illinois). Disponível em:                 
<http://sarielhp.org/teach/2004/b/webpage/lec/10_npc_notes.pdf>. Acesso em: junho de         
2014. 
 
6. Feofillof, Paulo (Sept 2013) (IME­USP) . “Subset­Sum” Disponível em :                   
<http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/mochila­subsetsum.html> 
Acesso em: junho de 2014. 
 
7. Hans Kellerer; Ulrich Pferschy; David Pisinger (2004), Knapsack problems, Springer. 
  
8. Karmarkar, Narenda; Karp, Richard M (1982), "The Differencing Method of Set                     
Partitioning", Technical Report UCB/CSD 82/113 (University of California at Berkeley) 
 
9. Korf, Richard E. (1998), "A complete anytime algorithm for number partitioning", Artificial                       
Intelligence 106 (2) <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.90.993>.       
Acesso em: junho de 2014. 
 
10. Oliveira, Igor Carboni. Complexidade computacional e o problema P vs NP­ Campinas,                       
[S.P. : s.n.], 2010. (1) 
11. Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009)                       
[1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw­Hill. 
 
11