Complexidade: problemas NP-completos

The greatest shortcoming of the human race is
our inability to understand the exponential function.

Albert A. Bartlett, Arithmetic, Population and Energy, YouTube video

 

Outras páginas deste sítio trataram da complexidade de algoritmos.  Esta página tratará de algo mais abstrato: a complexidade intrínseca de problemas.

A complexidade de um problema computacional é o consumo de tempo do melhor algoritmo possível para o problema.  (Convém lembrar que o melhor algoritmo conhecido atualmente não é, em geral, o melhor algoritmo possível.)  É claro que estamos nos referindo ao consumo de tempo no pior caso.

Esta página procura fazer uma classificação grosseira dos problemas com base na sua complexidade, separando os problemas mais fáceis (polinomiais) dos mais difíceis (NP-completos).  O assunto será discutido aqui de maneira informal e um tanto imprecisa.  Veja o verbete NP-complete na Wikipedia.

Problemas computacionais

Antes de discutir a complexidade de problemas, precisamos de um repertório de exemplos. Vários dos problemas na lista a seguir já foram discutidos em outras páginas deste sítio:

Os problemas dessa lista são exemplos de problemas de busca.   A seguinte lista dá exemplos de problemas de otimização:

Há uma relação íntima entre os problemas de otimização e os problemas de busca. Muitos problemas de otimização podem ser reduzidos aos correspondentes problemas de busca.

Esta página trata quase exclusivamente de problemas de busca, mas muitos dos conceitos estudados aqui podem ser aplicados aos problemas de otimização.

Algoritmos polinomiais

Dizemos que um algoritmo resolve um dado problema computacional se, ao receber qualquer instância do problema, devolve uma solução da instância ou informa que a instância não tem solução.

Um algoritmo que resolve um dado problema é polinomial se o seu consumo de tempo no pior caso é limitado por um polinômio no tamanho das instâncias do problema.  (No caso do problema da fatoração, por exemplo, o tamanho de uma instância é o número de dígitos de n, ou seja, cerca de log n.)  Em outras palavras, o algoritmo é polinomial se existe um número  i  (o mesmo para todas as instâncias) tal que o consumo de tempo do algoritmo é  Ο(Ni) ,  sendo N o tamanho da instância.

É polinomial, por exemplo, todo algoritmo que consome no máximo  100N4 + 300N2 + 5000  unidades de tempo, sendo N o tamanho da instância.  (Também é polinomial todo algoritmo que consome no máximo 200N9 log N unidades de tempo, pois 200N9 log N < 200N10.)

Algoritmos polinomiais são considerados rápidos  (ainda que seja difícil aceitar como rápido um algoritmo que consome tempo proporcional a N500, por exemplo).  Algoritmos não polinomiais — como, por exemplo, os que consomem tempo proporcional a 2N ou a 1.1N — são considerados inaceitavelmente lentos  (ainda que possam ser úteis para valores muito modestos de N).

Exercícios 1

  1. Descreva algoritmos polinomiais para cada um dos seguintes problemas:  quadrado perfeito, equação do segundo grau, divisor comum grande, subsequência crescente longa e caminho curto.
  2. Descreva um algoritmo polinomial para o problema da cobertura pequena.
  3. [CLRS 34.1-4]  O algoritmo Mochila-Prog-Din discutido em outra página é polinomial?
  4. Descreva informalmente um algoritmo (não necessariamente polinomial) que resolva o problema do ciclo hamiltoniano.
  5. Discuta a seguinte variante do problema do ciclo hamiltoniano: Dado um grafo e uma lista de todas as permutações de vértices do grafo, encontrar um ciclo hamiltoniano no grafo ou constatar que tal ciclo não existe. Descreva um algoritmo polinomial que resolva o problema.
  6. Descreva informalmente um algoritmo (não necessariamente polinomial) que resolva o problema da fatoração.
  7. Suponha que as instâncias de um certo problema são pares de cadeias de caracteres. O tamanho de uma instância é então da forma  N+M,  onde N é o comprimento da primeira cadeia do par e M é o comprimento da segunda cadeia. Suponha que tenho um algoritmo para o problema que consome Ω(N 2M) unidades de tempo. Mostre que o algoritmo não é polinomial.
  8. Suponha que cada instância de um certo problema consiste em um número natural k, um número natural n e um vetor x1,…, xn cujos componentes são elementos do conjunto {1,2,3}.  Um algoritmo que resolve qualquer instância do problema em  Ο(kn² log n unidades de tempo é polinomial?

Problemas polinomiais e a classe P

Um problema computacional é polinomial se existe um algoritmo polinomial para o problema.  Problemas desse tipo são considerados tratáveis ou fáceis.

Exemplos de problemas polinomiais:  o problema da equação do segundo grau, o problema do divisor comum grande, o problema da subsequência crescente longa, o problema do caminho curto.

A classe P de problemas é o conjunto de todos os problemas polinomiais.  (A bem da verdade, essa definição está tecnicamente incorreta, pois deveria se restringir aos problemas de decisão, problemas que só admitem soluções sim e não. A rigor, deveríamos dizer classe FP no lugar de classe P.)

Um problema é não polinomial se não existe algoritmo polinomial que resolva o problema.  (Cuidado! Não use a sigla NP como abreviatura de não polinomial!)   Problemas desse tipo são considerados intratáveis.

Não é fácil dar bons exemplos de problemas não polinomiais (veja o roadblock problem).  Suspeita-se que o problema do ciclo hamiltoniano não é polinomial. Paira uma suspeita análoga sobre o problema da fatoração, o problema da mochila valiosa, e muitos outros. Mas ainda estamos longe da comprovação dessas suspeitas.

(Para além dos problemas não polinomiais, existem problemas insolúveis, também conhecidos como indecidíveis. Para esses problemas, não existe algoritmo algum. É o caso, por exemplo, do problema das equações diofantinas.)

Exercícios 2

  1. Discuta a seguite afirmação:  Se X é um problema não polinomial então todas as instâncias de X são difíceis (ou seja, não podem ser resolvidas em tempo polinomial).
  2. Mostre que os seguintes problemas estão na classe P:  quadrado perfeito, equação do segundo grau, divisor comum grande, subsequência crescente longa e caminho curto.

A classe NP de problemas

A partir desse ponto, é preciso restringir ligeiramente nossa atenção aos problemas que são razoáveis no seguinte sentido:  é fácil reconhecer uma solução de uma instância do problema quando se está diante de uma.  (É difícil imaginar um problema que não tenha essa propriedade… ) 

Mais precisamente, um problema X é polinomialmente verificável se

é possível verificar, em tempo polinomial, se uma suposta solução de uma instância de X é de fato uma solução,

ou seja, se existe um algoritmo que, ao receber uma instância I de X e uma suposta solução S de I, responde sim ou não conforme S seja ou não solução de I,  e  consome tempo limitado por um polinômio no tamanho de I para responder sim(Segue daí, em particular, que as soluções são curtas, ou seja, o tamanho de uma solução é polinomial no tamanho da instância.)

O conjunto dos problemas polinomialmente verificáveis constitui a  classe NP  de problemas.  (Cuidado!  NP não é abreviatura de não polinomial mas sim de nondeterministic polynomial.) 

(A bem da verdade, essa definição da classe NP é tecnicamente incorreta, pois deveria ser aplicada somente a problemas de decisão, ou seja, problemas que só admitem as soluções sim e não.  A rigor, deveríamos escrever FNP no lugar de NP.)

Todos os problemas na primeira das duas listas de exemplos acima pertencem à classe NP.  Segue a discussão de alguns desses exemplos:

Não é fácil dar bons exemplos de problemas que não estejam na classe NP.  Um exemplo bobo é o problema de construir uma lista de todos os subconjuntos de {1, 2, …, n} uma vez dado n. Um exemplo melhor é o roadblock problem.

Suspeita-se que muitos problemas de otimização não estão na classe NP. No caso do problema do ciclo máximo, por exemplo, embora seja fácil verificar se uma dada sequência de vértices é um ciclo, não se conhece uma maneira eficiente de verificar que o ciclo é máximo.  (No entanto, o problema do máximo divisor comum está em NP pois está em P, como mostra o algoritmo de Euclides.)

Exercícios 3

  1. Mostre que os seguintes problemas estão na classe NP:  divisor comum grande, soma de subconjunto, mochila valiosa, subsequência crescente longa, caminho curto, caminho longo, clique grande, cobertura pequena.

A questão P = NP?

É fácil entender que a classe NP inclui a classe P, ou seja, que todo problema polinomial é polinomialmente verificável.  O bom senso sugere que P é apenas uma pequena parte de NP.  Surpreendentemente, ninguém encontrou ainda um problema de NP que não esteja em P, isto é, um problema polinomialmente verificável para o qual não existe algoritmo polinomial.

Esta situação abre caminho para a suspeita de que talvez  P seja igual a NP .   A maioria dos especialistas não acredita nessa possibilidade, entretanto.

Veja o verbete P versus NP problem na Wikipedia.  Veja também página de G. Woeginger com um histórico de provas frustadas de P=NP e P≠NP (O Instituto Clay de Matemática oferece um prêmio de um milhão de dólares pela solução da questão P=NP?.)

Reduções e a complexidade relativa de problemas

O status de muitos problemas da classe NP é desconhecido:  não se sabe se o problema está na classe P ou não.  Diante disso, é uma boa ideia investigar a complexidade relativa dos problemas da classe NP.  Trata-se de verificar se um dado problema Y é mais fácil ou mais difícil que um outro problema X (talvez mais bem-conhecido).

Informalmente, dizemos que um problema Y não é mais difícil que um problema X se Y for um subproblema, ou caso particular, de X.   Exemplos:

Para formalizar esse conceito, recorremos à ideia de redução polinomial:  Dizemos que um problema Y não é mais difícil que — ou que é polinomialmente redutível a — um problema X  se qualquer algoritmo para X pode ser usado para resolver Y em três passos:

  1. transforme a instância dada de Y, em tempo polinomial, numa instância de X,
  2. submeta a instância de X ao algoritmo para X, que produz uma solução S,
  3. transforme S, em tempo polinomial, numa solução da instância de Y.

(A expressão tempo polinomial é sempre relativa ao tamanho da instância de Y.)

Se Y não é mais difícil que X e X está na classe P então Y também está na classe P.  Dito de outra maneira:  se Y não está na classe P e Y não é mais difícil que X então X também não está na classe P.

(Eis outra maneira, mais ou menos equivalente, de definir redução polinomial:  Um problema Y é polinomialmente redutível a um problema X  se existe um algoritmo que resolve Y usando uma subrotina hipotética que resolve X de tal modo que se a subrotina for polinomial o algoritmo para Y também é polinomial.)

Exercícios 4

  1. Mostre que o problema do quadrado perfeito não é mais difícil que o problema da equação do segundo grau.  Reciprocamente, mostre que o problema da equação do segundo grau não é mais difícil que o problema da raiz quadrada.
  2. Mostre que o problema do ciclo hamiltoniano é polinomialmente redutível ao problema do ciclo longo.  Mostre a recíproca.
  3. Mostre que o problema da cobertura pequena de um grafo não é mais difícil que o problema da clique grande.  (Comece por analisar a relação entre coberturas e conjuntos independentes. Um conjunto independente é um conjunto de vértices dois-a-dois não adjacentes.)  Mostre a recíproca.
  4. Suponha que os algoritmos A e B transformam cadeias de caracteres em outras cadeias de caracteres.  Suponha que A consome Ο(N2) unidades de tempo e B consome Ο(N4) unidades de tempo, sendo N é o número de caracteres da cadeia de entrada.  Considere agora o algoritmo AB que consiste na composição de AB, com B recebendo como entrada a saída de A.  Qual o consumo de tempo de AB?
  5. Mostre que todo problema da classe P é polinomialmente redutível ao problema do ciclo hamiltoniano.

Problemas NP-completos

Um problema X é  NP-difícil  se todos os problemas em NP não são mais difíceis que X.  Dito de maneira mais informal: um problema é NP-difícil se for tão difícil quanto qualquer problema em NP.  Um problema é  NP-completo  se for NP-difícil e estiver em NP. 

A existência de problemas NP-completos é um fato surpreendente e fundamental.  O fato foi demonstrado, por volta de 1970, por Steven Cook e Leonid Levin (independentemente).

Uma vez conhecido um problema NP-completo, o conceito de redução polinomial pode ser usado para mostrar que outro problema é NP-completo:  se Y é um problema NP-completo e Y não é mais difícil que um problema X então X também é NP-completo.

Por exemplo, são NP-completos os seguintes problemas:  soma de subconjunto, mochila valiosa, ciclo longo, caminho longo, ciclo hamiltoniano, clique grande, cobertura pequena, campo minado.   Uma lista com centenas de outros problemas NP-completos pode ser encontrada no livro de Garey e Johnson.  Veja também An Annotated List of Selected NP-complete Problems.

Para provar que P = NP, basta encontrar um algoritmo polinomial para um único problema NP-completo.  Mas ninguém conseguiu ainda realizar essa façanha.

Exercícios 5

  1. Digamos que X é um problema NP-completo. É verdade que todas as instâncias de X são difíceis?
  2. Mostre que o problema do campo minado é NP-completo.  Solução: veja artigo de Ian Steward no sítio do Clay Mathematics Institute.
  3. Suponha que P ≠ NP. Quais das seguintes afirmações podemos inferir a respeito de um problema X?  (a) Se X é NP-completo então X não pode ser resolvido em tempo polinomial.  (b) Se X está em NP então X não pode ser resolvido em tempo polinomial.  (c) Se X está em NP mas não é NP-completo então X pode ser resolvido em tempo polinomial.  (d) Se X está em P então X não é NP-completo.

 


Apêndice: certificados de inexistência de solução

Muitos problemas têm instâncias que não admitem solução alguma. Como é possível provar que uma dada instância de um problema não admite solução?  Não estamos tratando aqui de como descobrir que a instância não tem solução, mas apenas de como tornar este fato evidente uma vez descoberto.

Para muitos problemas, existem certificados naturais e elegantes de inexistência de solução.  Todos consistem em trocar um não existe x por um existe y apropriado.  Eis alguns exemplos:

Em todos esses exemplo, o certificado de inexistência de solução é polinomialmente verificável no mesmo sentido em que, na definição da classe NP, uma solução é polinomialmente verificável.  Isso mostra que cada um dos problemas pertence à assim-chamada  classe coNP  e abre caminho para mostrar que os correspondentes problemas de otimização pertencem à classe NP.

Exercícios 6

  1. Suponha que um problema X está na classe P.  É verdade que X está na classe coNP?  Em outras palavras, é verdade que X admite um certificado de inexistência de solução que é polinomialmente verificável?
  2. É verdade que todo problema em NP também está em coNP?
  3. Mostre que cada um dos seguintes problemas de otimização está na classe NP:  máximo divisor comum, subsequência crescente máxima, caminho mínimo.

Valid HTML 4.01 Strict Valid CSS!