O maior problema da computação: P versus NP

Existem sete problemas matemáticos considerados tão difíceis e interessantes que o Instituto de Matemática Clay os chamou de problemas do milênio, e quem resolver qualquer um deles recebe um prêmio de um milhão de dólares. Um desses problemas diz respeito também à ciência da computação e se chama problema P versus NP. Vamos explicar do que trata esse problema.

Mas é bom não nos iludirmos: explicar isso não vai ser simples. Afinal, é um problema do milênio. Então vá preparar um bom chá verde 🍵 e vamos lá. Primeiro vamos ver quatro problemas diferentes do mundo da computação e dos algoritmos. Vamos analisar os problemas e ver qual é a relação deles com as letrinhas P e NP.

Problema nº 1: encontrar o menor número

P vs. NP tem a ver com algoritmos e com a sua complexidade. Imagine que eu despejasse na sua frente cem papeizinhos, cada um com um número escrito, e pedisse que você encontrasse o papel em que está escrito o menor número. Quanto tempo você levaria?

Meio minuto? Dois minutos?

Essas são unidades de tempo que, na ciência da computação teórica, não nos interessam tanto assim. O que nos interessa é o número de operações. Poderíamos, então, perguntar de outro jeito: quantos papeizinhos preciso verificar para ter certeza de que encontrei o menor número? A resposta é que preciso verificar todos os papeizinhos — porque o menor número pode estar justamente no último. Se eu jogar cem papeizinhos na sua frente, você precisa verificar cem papeizinhos. Se eu jogar mil, você precisa verificar mil. Em geral, se eu jogar n papeizinhos na sua frente, você precisa verificar n papeizinhos.

Isso é o que chamamos de complexidade de um algoritmo. Se eu jogo n papeizinhos na sua frente e você precisa fazer n operações para encontrar o menor número, isso significa que esse algoritmo de busca do menor número tem complexidade n, que também chamamos de complexidade linear, porque a complexidade é descrita por uma função afim.

Muito bem, você passou pelos cem papeizinhos e anunciou que o menor número é 17. Como posso verificar se você está dizendo a verdade? Não existe outro jeito além de percorrer todos os papeizinhos de novo e conferir que em nenhum deles há um número menor. Ou seja, você precisa olhar n papeizinhos para encontrar o menor número e eu, para conferir, preciso fazer a mesma coisa. Portanto, a complexidade da verificação do resultado também é n, uma complexidade linear.

Existem algoritmos para os quais é mais fácil verificar o resultado do que encontrá-lo?

Problema nº 2: produto de um par

Imagine que eu despeje na sua frente duas pilhas de papeizinhos do mesmo tamanho, e em cada papelzinho há de novo um número. Agora eu pediria que você encontrasse um número da pilha A e um número da pilha B de modo que o produto deles seja 918. Por exemplo, vamos considerar estas pilhas de números:

$\begin{array}{rcl} A & = & {49, 11, 32, 54, 15} \\ B & = & {17, 64, 74, 61, 21} \end{array}$

Como podemos encontrar um par de números cujo produto seja 918? Bem, podemos simplesmente testar todas as possibilidades. Quantas serão? Bastante: serão 25. Começamos multiplicando o primeiro número da pilha A, isto é, o número 49, por cada número da pilha B:

$\begin{array}{rcl} 49 \cdot 17 & = & 833 \\ 49 \cdot 64 & = & 3136 \\ 49 \cdot 74 & = & 3626 \\ 49 \cdot 61 & = & 2989 \\ 49 \cdot 21 & = & 1029 \end{array}$

Nenhum par de números dá 918. Então tentamos o mesmo com os demais números da pilha A, isto é, mais cinco pares para o número 11, mais cinco pares para o número 32, mais cinco pares para o 54 e os últimos cinco pares para o 15. No total, podemos testar 25 pares de números. No fim, descobrimos que 54 · 17 = 918.

Qual é a complexidade desse algoritmo? O que nos interessa é quantos pares de números tivemos de multiplicar. As duas pilhas continham cinco papeizinhos, e tivemos de testar cada um dos cinco números da primeira pilha com cada um dos cinco números da segunda. No total, testamos 5 · 5 = 25 combinações. Se eu jogasse na sua frente duas pilhas de 10 papeizinhos, você teria de testar 10 · 10 = 100 combinações. Generalizando, se eu jogar na sua frente duas pilhas de n papeizinhos, você precisa testar n · n = n² combinações.

Dizemos que esse nosso algoritmo tem complexidade n², complexidade quadrática, porque ela é descrita por uma função quadrática.

Mas quão complexo será verificar o resultado? Se você me responder que 54 e 17 são números cujo produto dá 918, eu não preciso mais percorrer todos os pares de números das duas pilhas, como você teve de fazer. Basta multiplicar esse único par, 54 · 17, e vou saber se você tem razão ou não. Assim, enquanto para resolver esse problema é preciso calcular até n² produtos, para a verificação basta calcular um único produto. A verificação tem, portanto, complexidade constante 1.

Nisso essa tarefa difere bastante da anterior, em que precisávamos do mesmo número de passos para o cálculo em si e para a verificação posterior.

Essa tarefa também é muito mais complexa do que a anterior. Se eu despejasse na sua frente dez mil papeizinhos e quisesse encontrar o menor número, você provavelmente conseguiria encontrá-lo em um dia. Mas se eu despejasse na sua frente duas vezes dez mil papeizinhos e deixasse você procurar o produto, você teria de verificar dez mil vezes dez mil produtos, o que dá cem milhões de cálculos. Mesmo que você testasse um produto por segundo, levaria cerca de três anos.

Problema nº 3: soma de um subconjunto

Vamos ver o terceiro problema. Desta vez, eu despejo na sua frente doze papeizinhos com números e peço que você encontre uma quantidade qualquer de papeizinhos cuja soma dê zero. Por exemplo:

$A = {24, - 69, 1, - 15, - 76, - 60, 16, - 83, 48, - 22, 54, - 47}$

Escolha desses números um grupo qualquer cuja soma dê 0. Por exemplo, os números

$24 + 48 - 69 + 1$

dão soma 4 e, portanto, não são a resposta correta. A resposta correta é o grupo de números… e sabe de uma coisa? Tente encontrá-lo você mesmo, como lição de casa 😉. Existe um único grupo de números cuja soma dá 0. Pelo menos você vai experimentar como esse problema é difícil.

Agora precisamos saber a complexidade desse problema. O cálculo em si já não é totalmente trivial e é mais para quem gosta de detalhes. Se você tem curiosidade de saber como se calcula a complexidade desse problema, continue lendo. Caso contrário, pode pular para o próximo capítulo. ⏩

Então, como podemos encontrar um grupo de números cuja soma dê 0? Bem, simplesmente precisamos testar todas as combinações possíveis de números. Precisamos testar todos os pares de números, todas as trincas, quádruplas, quíntuplas etc., e para cada grupo precisamos verificar se a soma dá zero. Quantas combinações desse tipo existem?

Vamos mostrar isso em um conjunto menor de números. Quantos grupos diferentes de números, ou seja, subconjuntos, posso formar com os três números B = {5, 7, 9}? Ao todo são oito:

$\begin{array}{rcl} B_{1} & = & {} \\ B_{2} & = & {5} \\ B_{3} & = & {7} \\ B_{4} & = & {9} \\ B_{5} & = & {5, 9} \\ B_{6} & = & {5, 7} \\ B_{7} & = & {7, 9} \\ B_{8} & = & {5, 7, 9} \end{array}$

Repare que contamos também o subconjunto vazio B₁. Isso não é muito útil agora, mas, para ficar completo, deixamos o subconjunto vazio na lista. Para simplificar o cálculo, vamos associar a cada subconjunto um vetor binário. Um vetor binário é simplesmente uma sequência de zeros e uns, por exemplo 00101010. Vamos trabalhar com vetores binários de comprimento três. Associamos o vetor da seguinte forma: o vetor 101 é associado ao subconjunto que contém “o primeiro e o terceiro número do conjunto original, mas não o segundo”, isto é, ao conjunto {5, 9}. O vetor 110 é associado ao subconjunto que contém “o primeiro e o segundo número do conjunto original, mas não o terceiro”, isto é, ao conjunto {5, 7}, e assim por diante.

$\begin{array}{rcl} B_{1} = {} & \to & 000 \\ B_{2} = {5} & \to & 100 \\ B_{3} = {7} & \to & 010 \\ B_{4} = {9} & \to & 001 \\ B_{5} = {5, 9} & \to & 101 \\ B_{6} = {5, 7} & \to & 110 \\ B_{7} = {7, 9} & \to & 011 \\ B_{8} = {5, 7, 9} & \to & 111 \end{array}$

Vemos que cada subconjunto tem exatamente um vetor binário de comprimento três. E cada vetor binário de comprimento três corresponde a exatamente um subconjunto. Portanto, se calcularmos quantos vetores binários diferentes de comprimento n existem, obteremos o número de combinações diferentes que conseguimos montar quando temos n números diferentes na entrada. Vamos calcular.

Existem dois vetores binários de comprimento um: 0 e 1.

Obtemos os vetores binários de comprimento dois pegando todos os vetores binários de comprimento um e acrescentando 0 ao final de cada vetor: obtemos os vetores 00 e 10. Pegamos de novo todos os vetores de comprimento 1 e acrescentamos 1 ao final: 01 e 11. Assim, obtivemos todos os vetores de comprimento 2: 00, 01, 10 e 11.

Obtemos os vetores binários de comprimento três pegando todos os vetores binários de comprimento dois e acrescentando ao final um zero: 000, 010, 100 e 110, e um um: 001, 011, 101 e 111.

E assim por diante, para cada comprimento seguinte. Vemos que, quando aumentamos em um o comprimento do vetor binário, o número de vetores binários diferentes dobra. Para o comprimento quatro, obteríamos então um total de 2 · 2 · 2 · 2, que é 16, combinações diferentes.

Em geral, podemos concluir que, se temos um conjunto M com n elementos, o número de todos os subconjuntos desse conjunto M é igual ao número de todos os vetores binários diferentes de comprimento n, que é igual a

$\underset{n vezes}{\underset{⏟}{2 \cdot 2 \cdot \dots \cdot 2}} = 2^{n}$

2ⁿ ou n² — não dá no mesmo? Da água para o vinho 🤷‍♂

Existem, portanto, 2ⁿ subconjuntos diferentes que podemos formar a partir de um conjunto de n números. No nosso caso, temos n = 12 números e precisamos verificar 2¹² combinações diferentes, que são 4096 combinações. Dizemos que esse problema tem complexidade 2ⁿ, complexidade exponencial, porque ele é descrito por uma função exponencial.

Repare que o problema anterior tinha complexidade n², enquanto este tem complexidade 2ⁿ. Parece muito parecido, não é? Só que há uma grande diferença entre ter um expoente constante e ter a variável n no expoente. Repare que, quando n = 4, obtemos

$\begin{array}{rclrc} n^{2} & = & 4^{2} & = & 16 \\ 2^{n} & = & 2^{4} & = & 16 \end{array}$

Bem, até agora dá o mesmo resultado. E se n = 10?

$\begin{array}{rclrc} n^{2} & = & 10^{2} & = & 100 \\ 2^{n} & = & 2^{10} & = & 1024 \end{array}$

Opa, a função exponencial disparou e de repente é cerca de dez vezes maior que a quadrática. O que obtemos para n = 20?

$\begin{array}{rclrc} n^{2} & = & 20^{2} & = & 400 \\ 2^{n} & = & 2^{20} & = & 1 048 576 \end{array}$

Para n = 20, a complexidade exponencial tem um valor cerca de 2.600 vezes maior que a complexidade quadrática. Vemos, então, que a função exponencial cresce muito mais rápido que a função quadrática. Lembre-se disso da próxima vez que uma pandemia se espalhar pela população em ritmo exponencial.

Portanto, se eu jogasse na sua frente vinte papeizinhos, você teria de verificar 1.048.576 combinações. É bastante coisa.

Como verificamos se o resultado está correto?

Quanto tempo vou levar para verificar que o grupo de números encontrado realmente tem soma 0? Será bem rápido: simplesmente somo esse único grupo de números e, se a soma for igual a 0, você encontrou o grupo certo de papeizinhos; se a soma for outra, você encontrou o conjunto errado.

De novo vemos que conferir o resultado é muito mais simples do que encontrá-lo.

Problema nº 4: o problema do caixeiro-viajante

O problema do caixeiro-viajante é um dos problemas algorítmicos mais famosos. Em linhas gerais, temos um caixeiro-viajante que vende chuva. E esse caixeiro-viajante precisa viajar muito para ganhar a vida. Por isso, decidiu visitar 14 grandes cidades do Brasil. E, como não quer desperdiçar nada, decidiu encontrar o caminho mais curto possível que o leve por todas essas cidades. E a nossa tarefa é encontrar esse caminho mais curto.

Como podemos encontrar esse caminho mais curto? Testamos todas as possibilidades.

Podemos simplificar. Imagine que entre quaisquer duas cidades existe exatamente um caminho mais curto. Como podemos encontrar o caminho mais curto passando por todas as cidades? Temos 14 cidades. Então temos 14 opções de onde começar. Digamos que começamos em São Paulo!!! Para onde podemos ir a partir de São Paulo? Teoricamente, podemos ir para qualquer outra cidade. Ou seja, podemos escolher entre as 13 cidades restantes.

Já podemos calcular que temos 14 · 13 possibilidades de visitar as duas primeiras cidades — temos 14 opções de onde começar e depois podemos escolher entre as 13 cidades restantes.

Quando chegamos à segunda cidade, precisamos continuar. Já estivemos em duas cidades, então podemos seguir para uma das 12 cidades restantes. Temos, portanto, um total de 14 · 13 · 12 possibilidades de visitar as três primeiras cidades.

Depois de visitar a terceira cidade, precisamos escolher uma das 11 cidades restantes, depois uma das 10 cidades restantes e assim por diante.

Quando tivermos visitado todas, veremos que tínhamos ao todo a escolha entre

$14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

possibilidades. Isso pode lembrar o fatorial, que indicamos com um ponto de exclamação. Podemos dizer, então, que esse produto é igual a 14!:

$14! = 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

e, portanto, existem 14! caminhos que passam por todas as cidades. É muito? Bastante, porque

$14! = 87 178 291 200.$

Em geral, se procurássemos o caminho mais curto entre n cidades, teríamos de testar n! caminhos diferentes. A complexidade dessa solução é, portanto, n!.

Como verificaríamos que encontramos o resultado correto? Se você me dissesse que o caminho mais curto é de Curitiba a Salvador, depois a Recife etc., como posso verificar se você está dizendo a verdade? Bem, é bem difícil 🤷‍♂. Porque, olhando para esse caminho, não tenho como verificar facilmente se esse caminho em particular é o mais curto. Na verdade, preciso refazer o cálculo inteiro. A verificação do resultado tem, portanto, também complexidade n!.

As classes P e NP

Apresentamos quatro problemas e os algoritmos que os resolvem, e analisamos quão complexo é encontrar a solução e quão complexo é verificá-la. Podemos resumir tudo nesta tabela:

Problema	Complexidade da resolução	Complexidade da verificação
Menor número	n	n
Produto de um par	n²	1
Soma de um subconjunto	2ⁿ	n
Caixeiro-viajante	n!	n!

Agora vamos dividir os nossos problemas em dois grupos. O primeiro grupo será formado pelos problemas que são fáceis de resolver. São os problemas que podem ser resolvidos com complexidade n ou n² ou n³ ou n⁴ etc. Como expressões como n² são chamadas de polinômios, designamos essa classe de problemas pela letra P. Dizemos, então, que a classe P contém os problemas que podem ser resolvidos em tempo polinomial (= têm complexidade como n² ou n⁷). Em geral, são problemas que podem ser resolvidos de forma mais ou menos simples.

Na classe P estão, portanto, o problema nº 1, encontrar o menor número, porque a complexidade da sua resolução é n, e também o problema nº 2, produto de um par, porque a complexidade da sua resolução é n²; ambos são polinômios.

A segunda classe é a classe NP. Ela contém os problemas que podem ser verificados em tempo polinomial. Na classe NP estão, portanto, todos os problemas, exceto o último. Não sabemos verificar o problema do caixeiro-viajante em tempo polinomial. Os três problemas anteriores podem ser verificados em tempo polinomial.

Não sabemos nem resolver nem verificar o problema do caixeiro-viajante em tempo polinomial. Para o problema do caixeiro-viajante precisaríamos, portanto, de mais uma classe, que contivesse problemas ainda mais difíceis. Essa classe existe, mas por enquanto não é interessante para nós.

É evidente que a classe P é um subconjunto da classe NP. Ou seja, todo problema que está na classe P está também na classe NP. Isso faz sentido — se conseguimos resolver um problema em tempo polinomial, conseguimos também verificar o resultado em tempo polinomial.

O problema P vs. NP

E o contrário também vale? Todo problema da classe NP está também na classe P? Ou seja, se existe um modo de verificar o resultado de um problema em tempo polinomial, existe também um algoritmo que resolveria esse problema em tempo polinomial?

Por exemplo, sabemos que conseguimos verificar o resultado do problema nº 3, a soma de um subconjunto, em tempo polinomial. Mas, para resolvê-lo, usamos um algoritmo que não é polinomial: o algoritmo usado tem complexidade exponencial 2ⁿ. Mas será que temos certeza de que não existe nenhum algoritmo de complexidade polinomial para esse problema?

Não sabemos!

Poderia muito bem acontecer que, para todo problema que pode ser verificado em tempo polinomial, exista um algoritmo que resolve esse problema em tempo polinomial. Nós não sabemos. Não sabemos provar a existência desse algoritmo, mas também não sabemos refutar a existência dele.

Se, para todo problema da classe NP, existisse um algoritmo que o resolve em tempo polinomial, isso significaria que a classe NP é, na verdade, igual à classe P. Todos os problemas da classe P estariam na classe NP e todos os problemas da classe NP estariam na classe P — as duas classes seriam iguais, coincidiriam.

O problema P vs. NP é, portanto, a pergunta se a classe P coincide com a classe NP ou se se trata de duas classes diferentes de problemas.

Ou vale P = NP, ou vale P ≠ NP. Ninguém sabe qual das duas, e, se você descobrir, o que o espera é um prêmio de um milhão de dólares, glória eterna e provavelmente também o Prêmio Turing, que é uma espécie de Nobel dos cientistas da computação.

O que aconteceria se P = NP?

O que aconteceria se valesse P = NP? Bem, não é totalmente simples dizer o que aconteceria. Saberíamos que, para todos os problemas da classe NP, existe um algoritmo que os resolve em tempo polinomial. Por exemplo, que para o nosso problema nº 3, a soma de um subconjunto, existe um algoritmo que o resolve em tempo polinomial. Só que isso tem três pegadinhas:

Saber que esse algoritmo existe não significa que somos capazes de encontrá-lo. Simplesmente saberíamos que sim, existe um algoritmo que resolve o problema em tempo polinomial, mas talvez não soubéssemos construí-lo por mais cem anos. É algo parecido com o que aconteceu quando a teoria da relatividade geral previu a existência dos buracos negros, mas ainda levamos várias décadas para conseguir tirar a primeira “fotografia” de um buraco negro.
Existir um algoritmo que funciona em tempo polinomial, infelizmente, ainda não significa que ele seja rápido. Poderíamos encontrar um algoritmo de complexidade n¹⁰⁰. Afinal, a expressão n¹⁰⁰ também é um polinômio. Se compararmos as complexidades 2ⁿ e n¹⁰⁰, veremos que, enquanto n é relativamente pequeno, o algoritmo de complexidade 2ⁿ ainda precisa de menos operações. Por exemplo, para n = 20 vale 2²⁰ = 1.048.576, enquanto a expressão 20¹⁰⁰ resulta em um número com cerca de 130 algarismos, que é cerca de 120 ordens de grandeza maior que 1.048.576. Nosso algoritmo polinomial seria, portanto, na prática, mais lento que o exponencial. Pelo menos enquanto n for relativamente pequeno.
Se, ainda assim, conseguíssemos encontrar um algoritmo rápido que funcione em tempo polinomial, conseguiríamos resolver muitos problemas com mais rapidez e mais precisão. Isso, claro, é uma notícia positiva, mas tem também o seu lado negativo. Existe uma área que depende de alguns problemas serem difíceis de resolver: a criptografia. Poderia acontecer, então, de ficar muito mais fácil quebrar as cifras atuais.

Intermezzo: como você leu até aqui, vou revelar, como recompensa, que a solução do problema nº 3 é 24 + 1 − 60 + 16 − 83 + 48 + 54.

O que aconteceria se P ≠ NP?

Se as classes de problemas P e NP fossem diferentes, não aconteceria muita coisa, porque isso é mais ou menos o status quo. No momento, não temos nenhum algoritmo que resolva em tempo polinomial algum problema difícil de NP, e, se alguém provasse que P ≠ NP, as coisas simplesmente ficariam assim para sempre. Uma sensação muito maior seria a prova de que P = NP.

Referências na cultura pop

Em um episódio dos Simpsons, vemos Homer entrar em uma espécie de realidade alternativa, na qual lhe é revelado que P = NP. Disponível no youtube.com.
Já em Futurama, vemos que eles têm no depósito duas pastas, uma chamada P e outra chamada NP. Disponível no youtube.com.
O segundo episódio da segunda temporada da série Elementary, intitulado “Solve for X”, trata do assassinato de um matemático que provavelmente resolveu o problema P versus NP.

« Anterior: Quanto é 1 + 2 + 5 · 0? Sobre a prioridade da multiplicação

Próximo: O método de Trachtenberg para somar rapidamente »