Outras páginas deste sítio trataram da complexidade — ou seja, do consumo de tempo — de algoritmos. Esta página tratará de algo mais abstrato: a complexidade computacional intrínseca de problemas. (Tenho outra página que trata do assunto de maneira mais informal, menos técnica.)
Veja o capítulo 34 de CLRS e o capítulo 8 de KT. Veja também o verbete NP-complete na Wikipedia.
Comecemos por restringir um pouco o tipo de problemas em estudo. Um problema computacional é de decisão se cada uma de suas instâncias admite uma e apenas uma de duas respostas: SIM e NÃO. Diremos que uma instância é positiva se tem solução SIM e negativa em caso contrário. Eis alguns exemplos de problemas de decisão:
É evidente que há uma relação íntima entre esses problemas de decisão e os exemplos da página Introdução à teoria da complexidade.
Para tornar as coisas precisas, é necessário padronizar o formato das instâncias dos problemas. Suporemos que todas as instância são cadeias de caracteres. O tamanho de uma instância é então o comprimento da correspondente cadeia de caracteres. Por exemplo,
(Veja observações sobre o algoritmo de programação dinâmica para o problema da mochila.)
Dizemos que um algoritmo resolve um determinado problema de decisão se, ao receber qualquer das instâncias do problema, devolve SIM se a instância for positiva e NÃO se a instância for negativa.
Um algoritmo que resolve um problema é polinomial se o seu consumo de tempo no pior caso é limitado por uma função polinomial dos tamanhos das instâncias. Em outras palavras, o algoritmo é polinomial se existe um número j tal que o consumo de tempo do algoritmo é
Ο(N j)
sendo N o tamanho de uma instância. É polinomial, por exemplo, todo algoritmo que consome Ο(N9 log N) unidades de tempo.
Algoritmos polinomiais são considerados rápidos. Algoritmos não polinomiais são considerados inaceitavelmente lentos.
Um problema é polinomial se existe um algoritmo polinomial que resolve o problema. Problemas desse tipo são considerados tratáveis. Eis alguns exemplos de problemas polinomiais: QUADRADO-PERFEITO, EQ-GRAU-2, SUBSEQ-CRESC-LONGA, CAMINHO-CURTO.
Um problema é não polinomial se nenhum algoritmo polinomial resolve o problema. Problemas desse tipo são considerados intratáveis. Não é fácil dar exemplos interessantes de problemas não polinomiais. (Um exemplo bobo é o problema de construir uma lista de todos os subconjuntos de {1,2,…,n}, uma vez dado n.) Suspeita-se que os seguintes sejam desse tipo: MOCHILA-VALIOSA, CAMINHO-LONGO, CICLO-LONGO, CICLO-HAMILT, CLIQUE-GRANDE, COBERTURA-PEQUENA.
(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 EQ-DIOFANTINA.)
A classe P de problemas é o conjunto de todos os problemas de decisão polinomiais. O status de muitos problemas de decisão é, ainda, desconhecido: não sabemos se o problema está em P ou fora de P.
Diante da dificuldade de decidir se um determinado problema está ou não em P, é interessante estudar a complexidade relativa de problemas. Antes de fazer isso, entretanto, é preciso introduzir os conceitos de certificado e algoritmo verificador.
Um algoritmo verificador para um problema de decisão recebe dois objetos: uma instância do problema e uma cadeia de caracteres que chamaremos de certificado. (A ideia é que o certificado seja uma "prova" de que a instância é positiva. Num certo sentido, o conceito de certificado substitui o conceito de solução, que não faz sentido em problemas de decisão.) Ao receber esses dois objetos, o verificador pode responder SIM ou NÃO. Se responder SIM, dizemos que o verificador aceitou o certificado.
Observe que o conceito de verificador é assimétrico: ele cuida apenas das instâncias positivas do problema.
Um verificador para um determinado problema de decisão é polinomial se satisfaz as seguintes condições:
É claro que a limitação polinomial do consumo de tempo faz com que o tamanho de um certificado aceitável também seja limitado por um polinômio no tamanho da instância. Ou seja, os certificados aceitáveis devem ser "curtos".
Alguns exemplos de certificados e algoritmos verificadores:
A classe NP de problemas é o conjunto de todos os problemas de decisão para os quais existem verificadores polinomiais. [Cuidado: "NP" não é abreviatura de "não polinomial"! "NP" é abreviatura de "nondeterministic polynomial".]
Podemos dizer, informalmente, que um problema está em NP se possui um "certificado curto". (A classe NP corresponde à classe dos problemas que poderíamos chamar "razoáveis".)
Não é fácil dar bons exemplos de problemas que estejam fora de NP. Um exemplo bobo é o problema de construir uma lista de todos os subconjuntos de {1,2,…,n}, uma vez dado n.
Não é difícil mostrar que a classe NP inclui a classe P, ou seja, que todo problema polinomial de decisão está em NP.
Todos os problemas de decisão que mencionamos acima estão evidentemente em NP. Mas a pertinência de um problema de decisão à classe NP nem sempre é tão evidente, como mostra a seção seguinte.
Os problemas de decisão ocorrem, naturalmente, em pares complementares. O complemento de um problema de decisão X é o problema de decisão Y que se obtém trocando todas as respostas SIM por NÃO e vice versa. Mais precisamente, Y é complemento de X se tem as mesmas instâncias que X mas toda instância positiva de X é negativa em Y e vice-versa. Por exemplo, o complemento do problema NÚMERO-COMPOSTO é o seguinte problema
Os complementos dos problemas EQ-GRAU-2, CICLO-LONGO e CICLO-HAMILT consistem no seguinte:
A classe coNP de problemas é o conjunto de todos os problemas de decisão cujo complemento está em NP. (Podemos dizer, informalmente, que coNP é a classe dos problemas de decisão que têm verificadores polinomiais para a resposta NÃO.) É fácil mostrar que a classe coNP inclui a classe P.
Considere alguns exemplos:
(A propósito: descobriu-se recentemente que o problema NÚMERO-PRIMO está em P. Portanto, o problema NÚMERO-COMPOSTO também está em P. Acredita-se, entretanto, que o problema FATORAÇÃO não está em P.)
Como já observamos, P é parte de NP. O bom senso sugere que P é apenas uma pequena parte de NP. Surpreendentemente, ninguém conseguiu ainda encontrar um problema de NP que não esteja em P.
Essa situação abre caminho para a suspeita de que P seja, talvez, igual a NP. Mas a maioria dos especialistas não acredita nessa possibilidade. [O Instituto Clay de Matemática oferece um milhão de dólares pela solução da questão "P=NP?".]
Veja verbete P = NP problem na Wikipedia. Veja também página de Woeginger com um histórico de provas frustadas de "P=NP" e "P≠NP".
Diante da dificuldade de decidir se um dado problema está em P, é interessante estudar a complexidade relativa dos problemas da classe NP. Dados dois problemas X e Y em NP, gostaríamos de poder dizer algo como "X é tão difícil quanto Y".
Um problema de decisão Y é redutível a um problema de decisão X se existe um algoritmo que transforma qualquer instância J de Y em uma instância I de X tal que J é positiva se e somente se I é positiva. Pode-se dizer, muito informalmente, que Y é redutível a X se Y for um "subproblema", ou "caso particular", de X.
Estamos interessados apenas em reduções polinomiais, ou seja, reduções em que o algoritmo de redução é polinomial. Se existe uma redução polinomial de X a Y, escrevemos X ≤P Y . Alguns exemplos:
Para quaisquer dois problemas X e Y na classe NP, se X está em P e existe uma redução polinomial de Y a X então Y também está em P. De fato, dada uma instância J de Y, basta reduzir J a uma instância I de X e em seguida submeter I a um algoritmo polinomial que resolve X.
Um problema de decisão X é completo em NP (ou NP-completo) se X está em NP e qualquer outro problema em NP pode ser polinomialmente reduzido a X. (Informalmente, X é NP-completo se for tão difícil quanto qualquer outro problema em NP.)
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 provar que P = NP basta encontrar um algoritmo polinomial para um único problema NP-completo.
A classe NPC é o conjunto de todos os problemas completos em NP. Portanto, NPC é a classe dos problemas mais "difíceis" de NP.
Eis alguns problemas em NPC: CICLO-HAMILT, CICLO-LONGO, CAMINHO-LONGO, CLIQUE-GRANDE, COBERTURA-PEQUENA, SUBSET-SUM, MOCHILA-VALIOSA. (Não se sabe, entretanto, se FATORAÇÃO está em NPC.)
Uma lista com centenas de problemas NP-completos pode ser encontrada no livro de Garey e Johnson. Veja também An Annotated List of Selected NP-complete Problems.