Introdução informal à complexidade de problemas

"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 computacional intrínseca de problemas.

A complexidade de um problema é o consumo de tempo do melhor algoritmo possível para o problema. (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, ou seja, ao consumo de tempo para as instâncias mais "difíceis" do problema.

O assunto será discutido aqui de maneira informal e portanto imprecisa. Para uma exposição mais técnica, veja a página Problemas NP-completos. Veja também o verbete NP-complete na Wikipedia.

Problemas computacionais

Precisamos de um repertório de exemplos. Vários exemplos de problemas já foram arrolados em outra página. Seguem mais alguns:

Quadrado perfeito: Dado um número natural n, encontrar um número natural x tal que x² = n ou constatar que tal x não existe.
Equação inteira do segundo grau: Dados números inteiros a, b e c, encontrar um número inteiro x tal que ax² + bx + c = 0 ou constatar que tal x não existe.
Fatoração: Dado um número natural n, encontrar um número natural p, maior que 1 e menor que n, que seja divisor n ou constatar que tal p não existe.
Máximo divisor comum: Encontrar o maior divisor comum de dois números naturais m e n.
Divisor comum grande: Dados números naturais m, n e k, encontrar um divisor comum de m e n que seja maior que k ou constatar que tal divisor não existe.
Subsequência crescente máxima: Dada uma sequência s₁,…,s_n de números naturais, encontrar uma subsequência crescente máxima de s₁,…,s_n.
Subsequência crescente longa: Dada uma sequência s₁,…,s_n de números naturais e um número natural k, encontrar uma subsequência crescente de s₁,…,s_n que tenha comprimento maior que k ou constatar que tal subsequência não existe.
Mochila: Dados números naturais p₁,…,p_n, v₁,…,v_n e c, encontrar um subconjunto K de {1,…,n} tal que a soma dos p_k para k em K não passe de c e a soma dos v_k para k em K seja máxima.
Caminho mínimo: Dados vértices r e s de um grafo, encontrar um caminho de comprimento mínimo de r a s no grafo ou constatar que não há caminho algum de r a s.
Caminho máximo: Dados vértices r e s de um grafo, encontrar um caminho de r a s que tenha comprimento máximo ou constatar que não há caminho algum de r a s.
Ciclo máximo: Encontrar um ciclo de comprimento máximo num grafo dado ou constatar que o grafo não tem ciclo algum.
Ciclo hamiltoniano: Encontrar um ciclo hamiltoniano (ou seja, um ciclo que passe por todos os vértices) num grafo dado ou constatar que tal ciclo não existe.
Ciclo longo: Dado um grafo e um número k, encontrar um ciclo de comprimento maior que k ou constatar que o grafo não tem tal ciclo.
Clique grande: Dado um grafo e um número k, encontrar uma clique com k ou mais vértices ou constatar que tal clique não existe.
Cobertura pequena: Dado um grafo e um número k, encontrar uma cobertura com menos que k vértices ou constatar que tal cobertura não existe.

(Observe que há uma relação íntima entre o problema do ciclo hamiltoniano e o problema do ciclo longo. Há relações análogas entre vários outros pares de problemas.)

Exercícios

Mostre que um algoritmo para o problema da equação do segundo grau pode ser usado para resolver o problema do quadrado perfeito. Reciprocamente, mostre como um algoritmo para o problema do quadrado perfeito pode ser usado para resolver o problema da equação do segundo grau.
Mostre que um algoritmo para o problema do máximo divisor comum pode ser usado para resolver o problema do divisor comum grande. Reciprocamente, mostre como um algoritmo para o problema do divisor comum grande pode ser usado para resolver o problema do máximo divisor comum.
Mostre que um algoritmo para o problema do ciclo longo pode ser usado para resolver o problema do ciclo hamiltoniano. Como um algoritmo para o problema do ciclo hamiltoniano poderia ser usado para resolver o problema do ciclo longo?

Algoritmos polinomiais

Dizemos que um algoritmo resolve um dado problema se, ao receber qualquer instância do problema, devolve uma solução da instância ou diz 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 uma função polinomial dos tamanhos das instâncias do problema.

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

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

Exercícios

Descreva informalmente um algoritmo (não necessariamente polinomial) que resolva o problema do ciclo hamiltoniano.
Discuta a seguinte variante do problema do ciclo hamiltoniano: Dado um grafo e uma lista de todas as permutações de vértices de um grafo, encontrar um ciclo hamiltoniano no grafo ou constatar que tal ciclo não existe. Descreva um algoritmo polinomial para o problema.
Descreva informalmente um algoritmo (não necessariamente polinomial) que resolva o problema da fatoração.

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 do ponto de vista computacional.

Exemplos de problemas polinomiais: o problema da equação do segundo grau, o problema do máximo divisor comum, o problema do caminho mínimo, o problema da subsequência crescente máxima.

A classe P de problemas é o conjunto de todos os problemas polinomiais. [A rigor, esta definição está incorreta, pois a classe P contém apenas os problemas polinomiais de decisão.]

Um problema é não polinomial se nenhum algoritmo polinomial resolve o problema. (Cuidado: não se trata de problemas para os quais algoritmos polinomiais não são conhecidos atualmente, pois tais algoritmos podem vir a ser descobertos no futuro.) Problemas desse tipo são considerados computacionalmente intratáveis.

A classe NP de problemas

O status de muitos problemas é desconhecido: não se sabe se o problema é polinomial ou não. Diante disso, é uma boa ideia investigar a complexidade relativa dos problemas. Trata-se de verificar se um dado problema Y é computacionalmente mais fácil ou mais difícil que um outro problema X (talvez mais bem-conhecido). Antes que isso possa ser feito, entretanto, é preciso restringir um pouco o universo dos problemas sob estudo.

Quais problemas devemos considerar "razoáveis"? Diremos que um problema é "razoável" se é fácil reconhecer uma solução do problema quando se está diante de uma. Mais precisamente, um problema computacional X é "razoável" se toda instância I de X satisfaz a seguinte condição:

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

Muitos dos problemas mencionados acima são "razoáveis". Considere os seguintes exemplos:

É fácil verificar se um dado inteiro x satisfaz a equação ax² + bx + c = 0. Essa verificação consome tempo limitado por um polinômio no tamanhos da instância (a,b,c) pois o valor absoluto de qualquer solução x da equação não é maior que o produto (|a|+1)(|b|+1)(|c|+1). Portanto, o problema da equação do segundo grau é "razoável".
É fácil verificar se um dado número natural p divide n. Ademais, a verificação consome tempo polinomial no tamanho da instância pois todo divisor de n é menor que n. Portanto, o problema da fatoração é "razoável".
O problema do ciclo longo é "razoável" pois é fácil verificar, em tempo polinomial, se um dado objeto é um ciclo no grafo e tem comprimento maior que k.
O problema do ciclo hamiltoniano é "razoável" pois é fácil verificar, em tempo polinomial, se um dado objeto é um ciclo no grafo e passa por todos os vértices do grafo.

O conjunto de todos os problemas "razoáveis" é (essencialmente) igual à classe NP de problemas. [Cuidado: "NP" não é abreviatura de "não polinomial" mas sim de "nondeterministic polynomial".]

(A rigor, não é correto confundir o conjunto dos problemas "razoáveis" com classe NP. A questão é que o conceito de solução — que serve de base para a ideia de problema "razoável" — não é suficientemente preciso. Considere, por exemplo, o problema do ciclo máximo. Por um lado, parece que deveríamos aceitar o problema como "razoável" uma vez que o problema do ciclo longo é "razoável". Por outro lado, o problema não parece "razoável" pois não está claro como verificar se um dado ciclo é máximo, ou seja, se não existe ciclo mais longo. Para contornar essas dificuldades, é preciso restringir nossa atenção a problemas "de decisão" e trocar o conceito de "solução" pelo de "certificado".)

A questão "P = NP?"

Não é difícil entender que a classe NP inclui a classe P, ou seja, que todo problema polinomial é "razoável". O bom senso sugere que P é apenas uma pequena parte de NP. Surpreendentemente, ninguém conseguiu ainda encontrar um problema de NP que comprovadamente não esteja em P, isto é, um problema "razoável" para o qual comprovadamente 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. [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?".]

A pergunta "P = NP?" por ser reformulada assim: "É verdade que todo problema cujas soluções podem ser conferidas por um algoritmo polinomial pode também ser resolvido por um algoritmo polinomial?"

Complexidade relativa de problemas

Podemos agora dizer algo sobre a complexidade relativa de problemas em NP. Um problema Y não é mais difícil que um outro problema X se Y for um "subproblema", ou "caso particular", de X. Exemplos:

O problema do quadrado perfeito não é mais difícil que o problema da equação do segundo grau.
O problema do ciclo hamiltoniano não é mais difícil que o problema do ciclo longo.
O problema da cobertura pequena de um grafo não é mais difícil que o problema da clique grande. (Por que?)

Para explicar um pouco melhor o conceito, diremos que um problema Y não é mais difícil que um problema X se qualquer algoritmo polinomial para X pode ser transformado num algoritmo polinomial para Y. O algoritmo para Y tem três etapas: primeiro, qualquer instância J de Y é transformada, em tempo polinomial, numa instância "equivalente" I de X; depois, a instância I é submetida ao algoritmo polinomial para X, que produz uma solução S; finalmente, S é transformada, em tempo polinomial, numa solução T de J. Assim, se X está em P e Y não é mais difícil que X então Y também está em P.

Problemas completos em NP

Um problema X é completo em NP, ou NP-completo, se X está em NP e todos os demais problemas em NP não são mais difíceis que X.

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

Para mostrar que P = NP basta encontrar um algoritmo polinomial para um único problema NP-completo. Portanto, os problemas NP-completos são os mais "difíceis" de NP.

Por exemplo, são NP-completos os problemas (de decisão derivados dos) seguintes: ciclo hamiltoniano, ciclo longo, clique grande, cobertura pequena, mochila. Uma lista com centenas de outros problemas NP-completos pode ser encontrada no livro de Garey e Johnson.

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

Nossa tentativa grosseira de definir a classe NP de problemas, trouxe à baila uma questão importante. Muitos problemas têm instâncias que não admitem solução. Como é possível "provar" ou "certificar" que uma dada instância de um problema não admite solução? Não estamos tratando aqui de como descobrir que uma dada instância não tem solução, mas apenas de, uma vez descoberta a inexistência de solução, como tornar este fato "evidente".

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

Problema do quadrado perfeito: Para mostrar que um número natural n não é um quadrado perfeito, basta exibir um número natural k tal que k² < n < (k+1)². Um tal k é um certificado de inexistência de solução.
Problema da equação do segundo grau: Para mostrar que não existe um inteiro x tal que ax² + bx + c = 0, basta verificar que (1) b²−4ac não é um quadrado perfeito, ou (2) b²−4ac é um quadrado perfeito mas nem (b²−4ac)^½ + b nem (b²−4ac)^½ − b são divisíveis por 2a. Assim, um certificado de inexistência de solução consiste em certificados para as condições (1) ou (2).
Problema do divisor comum grande: Para mostrar que não existe divisor comum de m e n que seja maior que k é suficiente exibir números inteiros (não necessariamente positivos) x e y tais que 0 < xm+yn ≤ k. Como qualquer divisor comum de m e n é também divisor de xm+yn, concluímos que todo divisor comum de m e n é menor ou igual a k. Assim, o par x,y é um certificado da inexistência de divisor comum grande. Todas as instâncias sem solução têm um tal certificado. (O algoritmo de Euclides calcula o certificado ao mesmo tempo que calcula um máximo divisor comum.)
Problema da fatoração: Existe um certificado muito interessante para as instância do problema que não têm solução, mas não tenho condições descrever o certificado aqui.
Problema da subsequência crescente longa: Suponha dada uma cobertura por subsequências estritamente decrescentes de uma sequência s₁,…,s_n de números naturais. Se a cobertura consiste em k sequências então é claro que nenhuma subsequência crescente de s₁,…,s_n pode ter comprimento maior que k. Assim, uma cobertura pequena por subsequências estritamente decrescentes é um certificado de inexistência de subsequência crescente longa. Todas as instâncias sem solução têm uma tal cobertura. (O algoritmo que calcula uma subsequência crescente máxima pode ser adaptado para determinar também um cobertura mínima.)
Problema do caminho mínimo: Seja R um conjunto de vértices que contém o vértice r mas não contém o vértice s. Suponha ainda que nenhuma aresta liga um vértice de R a um vértice fora de R. Se um tal R existe, é claro que não existe caminho de r a s. Assim, um tal R é um certificado de inexistência de solução para a instância em discussão. (Toda instância sem solução tem um tal certificado.)

Cada um desses exemplos mostra que o correspondente problema está na classe coNP.