Origens

Por que alguns problemas o computador resolve num piscar de olhos e outros levariam mais tempo do que a idade do universo? Essa é a pergunta da complexidade computacional, a área da ciência da computação que mede quão difícil é resolver um problema.

Antes dos computadores: Turing

Em 1936, antes mesmo de existirem computadores como os de hoje, o matemático Alan Turing imaginou uma máquina simples, capaz de executar qualquer cálculo passo a passo. Com ela, provou algo surpreendente: existem problemas que nenhum computador jamais vai resolver. O mais famoso é o problema da parada: não existe um programa capaz de olhar para qualquer outro programa e dizer, sempre, se ele vai terminar ou rodar para sempre. ^[20]

A carta de Gödel

Em 20 de março de 1956, o lógico Kurt Gödel escreveu uma carta ao matemático John von Neumann. Nela, perguntava quanto tempo uma máquina levaria para encontrar a prova de um teorema. Se fosse pouco, argumentava, o trabalho mental dos matemáticos em perguntas de sim ou não poderia ser feito por máquinas. Sem saber, Gödel tinha acabado de fazer a pergunta que hoje chamamos de P = NP. ^[18]

A área ganha nome

Em 1965, Juris Hartmanis e Richard Stearns publicaram um artigo que media o tempo dos algoritmos em função do tamanho do problema e deu nome à área: complexidade computacional. O trabalho rendeu aos dois o Prêmio Turing de 1993, o “Nobel da computação”. ^{[14] [10]} Na mesma época, Alan Cobham e Jack Edmonds propuseram uma regra que vale até hoje: um algoritmo é eficiente quando o seu tempo cresce como um polinômio, como n² ou n³, e não como uma exponencial, como 2ⁿ. ^[10]

Nasce a pergunta de 1 milhão de dólares

Em 1971, Stephen Cook mostrou que um problema de lógica chamado SAT é NP-completo, ou seja, um dos mais difíceis da classe NP. ^[17] Em 1972, Richard Karp mostrou que outros 21 problemas famosos eram tão difíceis quanto ele. ^[16] E, do outro lado da Cortina de Ferro, na União Soviética, Leonid Levin chegou à mesma ideia de forma independente, com publicação em 1973. ^[17] Em 2000, o Instituto Clay incluiu P versus NP entre os sete Problemas do Milênio, com um prêmio de 1 milhão de dólares para quem o resolver. ^[8]

Classificação

Algoritmo: uma receita de bolo

Um algoritmo é uma receita: uma lista de passos que, seguidos à risca, resolvem um problema. Para comparar receitas, os cientistas não medem o tempo no relógio, que depende de cada computador. Eles contam quantos passos a receita precisa conforme o problema cresce. O tamanho do problema se chama n: o número de itens de uma lista, de cidades num mapa ou de casas num tabuleiro.

Rápido e lento: polinomial contra exponencial

Imagine um computador que faz 1 bilhão de passos por segundo. Um algoritmo que precisa de n² passos resolve um problema com 100 itens em 10 microssegundos. Um algoritmo que precisa de 2ⁿ passos levaria 40 trilhões de anos para os mesmos 100 itens, cerca de 3 mil vezes a idade do universo. A diferença não está no computador: está na receita.

Por isso a regra de Cobham e Edmonds é tão útil: algoritmos polinomiais continuam viáveis quando o problema cresce; exponenciais, não. Nem os computadores mais rápidos compensam essa explosão.

P: fácil de resolver

A classe P reúne os problemas que um computador resolve em tempo polinomial. Ordenar uma lista de nomes, achar o caminho mais curto no GPS e até testar se um número gigante é primo estão em P. Este último só foi provado em 2002, por Manindra Agrawal e dois de seus alunos, Neeraj Kayal e Nitin Saxena. ^[5]

NP: fácil de verificar

A classe NP reúne os problemas em que, se alguém entregar uma resposta, você consegue conferir rapidamente se ela está certa. O Sudoku é o exemplo perfeito: resolver um tabuleiro gigante pode exigir tentativas sem fim, mas conferir um tabuleiro preenchido é só olhar linhas, colunas e quadrados.

Cuidado com uma confusão comum: NP não quer dizer “não polinomial”. Quer dizer “polinomial não determinístico”, como se o computador pudesse chutar a resposta certa e só precisasse conferi-la. Todo problema de P também está em NP: quem sabe resolver rápido também sabe conferir rápido.

NP-completo e NP-difícil

Dentro de NP estão os problemas mais difíceis de todos, os NP-completos. Eles têm uma propriedade mágica: se alguém descobrir um jeito rápido de resolver um deles, todos os problemas de NP passam a ter solução rápida. Já os NP-difíceis são pelo menos tão difíceis quanto os NP-completos, mas não precisam estar em NP: alguns nem têm resposta de sim ou não, e outros, como o problema da parada, nem sequer podem ser resolvidos.

Além de NP

Há problemas comprovadamente ainda mais difíceis. Descobrir a jogada perfeita num xadrez jogado num tabuleiro n × n, que pode crescer à vontade, exige tempo exponencial: esse problema está na classe EXP. ^[12] E, além de todos, estão os indecidíveis, como o problema da parada de Turing.

Seus jogos favoritos são difíceis

Os cientistas adoram provar que jogos são difíceis. Veja alguns resultados:

Em todos os casos, os resultados valem para versões generalizadas, com tabuleiros ou fases de qualquer tamanho. Um Sudoku 9 × 9 comum, um computador resolve num instante.

• “NP quer dizer não polinomial”

  Realidade: NP significa polinomial não determinístico, ou seja, fácil de verificar.

• “NP-difícil quer dizer impossível”

  Realidade: quer dizer que não se conhece atalho rápido para todos os casos. Casos pequenos ou comuns costumam ser resolvidos bem.

• “Um computador mais rápido resolve”

  Realidade: contra um crescimento exponencial, dobrar a velocidade quase não faz diferença.

• “O computador quântico resolve tudo”

  Realidade: os especialistas acreditam que nem ele resolve problemas NP-completos rapidamente. ^[2]

Relação matemática

Polinômios contra exponenciais

Toda a teoria se apoia numa comparação entre dois tipos de função. Num polinômio, o n fica na base e o expoente é fixo; numa exponencial, o n vai para o expoente:

Polinomial:   n²   n³   n¹⁰    → o expoente é fixo
Exponencial:  2ⁿ   3ⁿ   n!     → o n está no expoente (ou no fatorial)

n = 10:   n² = 100     2ⁿ = 1.024            n! = 3.628.800
n = 30:   n² = 900     2ⁿ = 1.073.741.824    n! ≈ 2,7 × 10³²

Por maior que seja o expoente de um polinômio, uma exponencial sempre acaba passando à frente. É por isso que a fronteira entre P e o resto é tão importante.

O caixeiro viajante

Um exemplo clássico: um entregador precisa visitar várias cidades e voltar ao ponto de partida pelo caminho mais curto. Com n cidades, existem (n − 1)! ÷ 2 rotas diferentes. Com 5 cidades, são 12 rotas. Com 25, são mais de 300 sextilhões: testar todas levaria cerca de 10 milhões de anos.

Existem algoritmos mais espertos, que evitam testar tudo, mas todos os que conhecemos e que dão a resposta exata para qualquer mapa continuam exponenciais. A versão de sim ou não do problema (“existe uma rota com menos de X quilômetros?”) é NP-completa, parente próxima do ciclo hamiltoniano da lista de Karp. ^[16]

Reduções: o tradutor entre problemas

A ferramenta matemática mais importante da área é a redução. Reduzir o problema A ao problema B é criar um tradutor rápido que transforma qualquer pergunta de A numa pergunta de B com a mesma resposta. Se B for fácil, A também será. Foi assim que Karp mostrou, em 1972, que 21 problemas eram NP-completos: Karp os ligou em cadeia, como dominós, a partir do SAT. ^[16]

Por que ninguém consegue provar?

Parece que bastaria provar que algum problema NP-completo exige tempo exponencial. Mas os matemáticos descobriram que as técnicas conhecidas não dão conta disso. Há pelo menos três “barreiras” provadas: a relativização (1975), as provas naturais (1994) e a algebrização (2008). Cada uma mostra que um tipo inteiro de argumento nunca vai resolver a questão. ^[4] Ou seja: para resolver P versus NP, vai ser preciso inventar matemática nova.

Relação filosófica

Criar é mais difícil que reconhecer?

Pense na diferença entre compor uma música e perceber que ela é bonita, ou entre inventar uma piada e rir dela. Reconhecer parece bem mais fácil que criar. P versus NP é a versão matemática dessa intuição. O cientista da computação Scott Aaronson escreveu: ^[1]

“Se P = NP, o mundo seria um lugar profundamente diferente do que costumamos imaginar. Não haveria valor especial em ‘saltos criativos’, nenhuma diferença fundamental entre resolver um problema e reconhecer a solução depois de encontrada. Todos que conseguissem apreciar uma sinfonia seriam Mozart.”

Máquinas matemáticas

Gödel já tinha percebido, em 1956, que a resposta mudaria o papel dos matemáticos: se achar provas fosse tão fácil quanto conferi-las, uma máquina poderia fazer boa parte do trabalho. ^[18] Hoje, programas de IA já ajudam a encontrar e checar provas, mas isso não resolve a questão: eles usam atalhos que funcionam em muitos casos, não em todos.

O que conta como conhecimento

Aaronson também defende que filósofos deveriam se importar com complexidade. Saber que uma resposta existe não é o mesmo que conseguir encontrá-la num tempo razoável. Cada posição de xadrez tem uma jogada perfeita, mas ninguém, nem computador algum, consegue calculá-la sempre. Para Aaronson, a eficiência muda perguntas antigas sobre o que significa conhecer, aprender e até pensar. ^[3]

Uma lei da natureza?

Há quem vá além e sugira que “problemas NP-completos são difíceis” poderia ser tratado como um princípio da física, assim como “nada viaja mais rápido que a luz”. Se nenhum sistema do universo, nem mesmo quântico, consegue resolvê-los rápido, isso diria algo sobre a própria natureza. ^[2]

Projeção de futuro

O que os especialistas apostam

Em 2019, o cientista da computação William Gasarch repetiu uma enquete com pesquisadores da área. Das 124 respostas, cerca de 80% disseram acreditar que P ≠ NP; entre quem mais estudou o problema, 99%. E 66% acharam que a questão será resolvida antes de 2100. ^[13]

Se P = NP

Lance Fortnow descreve esse cenário como um mundo em que quase tudo poderia ser otimizado, de rotas de entrega a remédios e materiais, e em que computadores encontrariam provas matemáticas sozinhos. O lado sombrio: a criptografia que protege senhas, bancos e mensagens depende de problemas difíceis e ficaria vulnerável se o algoritmo fosse prático. ^[11]

Se P ≠ NP

É o cenário mais provável. Os problemas difíceis continuam difíceis, e isso é bom para a segurança. Para enfrentá-los na prática, usamos aproximações (uma resposta boa, não perfeita) e heurísticas (atalhos que funcionam na maioria dos casos). É assim que aplicativos de entrega montam rotas todos os dias sem esperar milhões de anos.

E os computadores quânticos?

Eles não devem mudar esse quadro. Um computador quântico consegue fatorar números grandes muito rápido, com o algoritmo de Peter Shor, de 1994, o que ameaça parte da criptografia atual. Mas fatorar não é um problema NP-completo, e os especialistas acreditam que nem os computadores quânticos resolvem problemas NP-completos rapidamente. ^[2] Por precaução, o NIST publicou em 2024 padrões de criptografia pós-quântica, pensados para resistir também a eles. ^[19]

E a inteligência artificial?

A IA é ótima para achar boas respostas para problemas difíceis, como montar horários escolares ou planejar rotas, mas faz isso com heurísticas, sem garantia de acertar sempre. Ela não muda a classe de um problema. Talvez um dia ajude os matemáticos a encontrar a prova de P ≠ NP, mas, pelas barreiras que vimos, vai ser preciso uma ideia realmente nova.

Conclusão

A complexidade computacional nasceu de uma pergunta simples: quanto esforço é preciso para resolver um problema? Ela mostrou que existem problemas fáceis, difíceis e impossíveis, e que a diferença entre polinomial e exponencial vale mais do que qualquer computador novo.

P versus NP é, ao mesmo tempo, uma questão de matemática, de tecnologia e de filosofia. A resposta pode proteger ou expor os nossos segredos, dizer se a criatividade pode ser automatizada e revelar limites da própria natureza. E ela ainda está esperando alguém para encontrá-la. Quem sabe você?

Glossário essencial

Algoritmo

Lista de passos que resolve um problema, como uma receita.

Aproximação

Algoritmo que entrega uma resposta boa, com garantia de estar perto da melhor, sem ser necessariamente perfeita.

EXP

Problemas que podem ser resolvidos em tempo exponencial.

Heurística

Atalho que costuma funcionar bem na prática, mas sem garantia para todos os casos.

Indecidível

Problema que nenhum computador consegue resolver, como o problema da parada.

n

O tamanho do problema: itens de uma lista, cidades de um mapa, casas de um tabuleiro.

NP

Problemas cuja resposta, quando alguém a mostra, pode ser verificada em tempo polinomial.

NP-completo

Os problemas mais difíceis de NP: se um tiver solução rápida, todos terão.

NP-difícil

Problemas pelo menos tão difíceis quanto os NP-completos, estejam ou não em NP.

P

Problemas que podem ser resolvidos em tempo polinomial.

Redução

Tradução rápida de um problema em outro, com a mesma resposta.

SAT

Problema de decidir se uma fórmula lógica pode ser verdadeira; o primeiro NP-completo conhecido.

Tempo exponencial

Número de passos que cresce como 2ⁿ ou n!; explode rapidamente.

Tempo polinomial

Número de passos que cresce como n², n³ ou outra potência fixa de n; considerado eficiente.

Revisão rápida

Referências

1. Aaronson, S., “Reasons to believe”, setembro de 2006, Shtetl-Optimized.
2. Aaronson, S., “NP-complete Problems and Physical Reality”, 2005, scottaaronson.com.
3. Aaronson, S., “Why Philosophers Should Care About Computational Complexity”, agosto de 2011, arXiv:1108.1791.
4. Aaronson, S.; Wigderson, A., “Algebrization: A New Barrier in Complexity Theory”, 2008, scottaaronson.com.
5. Agrawal, M.; Kayal, N.; Saxena, N., “PRIMES is in P”, 2004, Annals of Mathematics 160.
6. Aloupis, G.; Demaine, E. D.; Guo, A.; Viglietta, G., “Classic Nintendo Games are (Computationally) Hard”, 2014, arXiv:1203.1895.
7. Ben-Ari, M., “Minesweeper as an NP-complete problem”, 2005, ACM SIGCSE Bulletin.
8. Clay Mathematics Institute, “P vs NP”, claymath.org.
9. Demaine, E. D.; Hohenberger, S.; Liben-Nowell, D., “Tetris is Hard, Even to Approximate”, 2003, csail.mit.edu.
10. Fortnow, L.; Homer, S., “A Short History of Computational Complexity”, 2003, lance.fortnow.com.
11. Fortnow, L., “The Golden Ticket: P, NP, and the Search for the Impossible”, abril de 2013, Princeton University Press.
12. Fraenkel, A. S.; Lichtenstein, D., “Computing a perfect strategy for n × n chess requires time exponential in n”, 1981, Journal of Combinatorial Theory A 31.
13. Gasarch, W.; Fortnow, L., “Third Poll on P vs NP and related Questions is out now!”, março de 2019, Computational Complexity blog.
14. Hartmanis, J.; Stearns, R. E., “On the computational complexity of algorithms”, 1965, Transactions of the AMS 117.
15. Kendall, G.; Parkes, A.; Spoerer, K., “A Survey of NP-Complete Puzzles”, 2008, ICGA Journal.
16. Wikipedia, “Karp’s 21 NP-complete problems”, en.wikipedia.org.
17. Wikipedia, “Cook–Levin theorem”, en.wikipedia.org.
18. Lipton, R. J., “The Gödel Letter”, rjlipton.com.
19. NIST, “Post-Quantum Cryptography FIPS Approved”, agosto de 2024, csrc.nist.gov.
20. Stanford Encyclopedia of Philosophy, “Turing Machines”, plato.stanford.edu.
21. Walsh, T., “Candy Crush is NP-hard”, março de 2014, arXiv:1403.1911.

Origins

Why can a computer solve some problems in the blink of an eye while others would take longer than the age of the universe? That is the question of computational complexity, the area of computer science that measures how hard it is to solve a problem.

Before computers: Turing

In 1936, before computers like today’s even existed, mathematician Alan Turing imagined a simple machine able to carry out any calculation step by step. With it, Turing proved something surprising: some problems can never be solved by any computer. The most famous is the halting problem: no program can look at every other program and always say whether it will finish or run forever. ^[20]

Gödel’s letter

On 20 March 1956, logician Kurt Gödel wrote a letter to mathematician John von Neumann. In it, Gödel asked how long a machine would take to find the proof of a theorem. If it were short, the argument went, the mental work of mathematicians on yes-or-no questions could be done by machines. Without knowing it, Gödel had just asked the question we now call P = NP. ^[18]

The field gets a name

In 1965, Juris Hartmanis and Richard Stearns published a paper that measured the time of algorithms as a function of the size of the problem and gave the field its name: computational complexity. The work earned both of them the 1993 Turing Award, the “Nobel Prize of computing”. ^{[14] [10]} Around the same time, Alan Cobham and Jack Edmonds proposed a rule still used today: an algorithm is efficient when its time grows like a polynomial, such as n² or n³, and not like an exponential, such as 2ⁿ. ^[10]

The million-dollar question is born

In 1971, Stephen Cook showed that a logic problem called SAT is NP-complete, that is, one of the hardest problems in the class NP. ^[17] In 1972, Richard Karp showed that 21 other famous problems were just as hard. ^[16] And on the other side of the Iron Curtain, in the Soviet Union, Leonid Levin reached the same idea independently, publishing it in 1973. ^[17] In 2000, the Clay Institute included P versus NP among its seven Millennium Prize Problems, with a 1 million dollar prize for whoever solves it. ^[8]

Classification

An algorithm is a recipe

An algorithm is a recipe: a list of steps that, followed exactly, solve a problem. To compare recipes, scientists do not measure clock time, which depends on each computer. They count how many steps the recipe needs as the problem grows. The size of the problem is called n: the number of items in a list, cities on a map or squares on a board.

Fast and slow: polynomial versus exponential

Imagine a computer that does 1 billion steps per second. An algorithm that needs n² steps solves a problem with 100 items in 10 microseconds. An algorithm that needs 2ⁿ steps would take 40 trillion years for the same 100 items, about 3,000 times the age of the universe. The difference is not in the computer: it is in the recipe.

That is why Cobham and Edmonds’s rule is so useful: polynomial algorithms stay practical as the problem grows; exponential ones do not. Not even the fastest computers can make up for that explosion.

P: easy to solve

The class P contains the problems a computer can solve in polynomial time. Sorting a list of names, finding the shortest path on a GPS and even testing whether a huge number is prime are in P. That last one was only proved in 2002, by Manindra Agrawal and two students, Neeraj Kayal and Nitin Saxena. ^[5]

NP: easy to check

The class NP contains the problems where, if someone hands you an answer, you can quickly check whether it is right. Sudoku is the perfect example: solving a giant board may take endless tries, but checking a filled-in board just means looking at rows, columns and squares.

Watch out for a common mix-up: NP does not mean “non-polynomial”. It means “nondeterministic polynomial”, as if the computer could guess the right answer and only needed to check it. Every problem in P is also in NP: if you can solve something fast, you can also check it fast.

NP-complete and NP-hard

Inside NP are the hardest problems of all, the NP-complete ones. They have a magical property: if someone finds a fast way to solve one of them, every problem in NP gets a fast solution. NP-hard problems are at least as hard as the NP-complete ones, but they do not have to be in NP: some do not even have a yes-or-no answer, and others, such as the halting problem, cannot be solved at all.

Beyond NP

Some problems are proven to be even harder. Finding the perfect move in chess played on an n × n board, which can grow as large as you like, requires exponential time: that problem is in the class EXP. ^[12] And beyond everything are the undecidable problems, such as Turing’s halting problem.

Your favorite games are hard

Scientists love proving that games are hard. Here are some results:

In every case, the results apply to generalized versions, with boards or levels of any size. A normal 9 × 9 Sudoku is solved by a computer in an instant.

• “NP means non-polynomial”

  Reality: NP means nondeterministic polynomial, that is, easy to check.

• “NP-hard means impossible”

  Reality: it means no fast shortcut is known for every case. Small or typical cases are often solved well.

• “A faster computer will solve it”

  Reality: against exponential growth, doubling the speed makes almost no difference.

• “Quantum computers solve everything”

  Reality: experts believe not even they can solve NP-complete problems quickly. ^[2]

The mathematics

Polynomials versus exponentials

The whole theory rests on a comparison between two kinds of function. In a polynomial, n is the base and the exponent is fixed; in an exponential, n moves into the exponent:

Polynomial:   n²   n³   n¹⁰    → the exponent is fixed
Exponential:  2ⁿ   3ⁿ   n!     → n is in the exponent (or the factorial)

n = 10:   n² = 100     2ⁿ = 1,024            n! = 3,628,800
n = 30:   n² = 900     2ⁿ = 1,073,741,824    n! ≈ 2.7 × 10³²

However large the exponent of a polynomial, an exponential always ends up overtaking it. That is why the border between P and the rest matters so much.

The traveling salesperson

A classic example: a delivery driver must visit several cities and return to the starting point by the shortest route. With n cities there are (n − 1)! ÷ 2 different routes. With 5 cities there are 12. With 25 there are over 300 sextillion: trying them all would take about 10 million years.

Cleverer algorithms exist that avoid trying everything, but every known algorithm that gives the exact answer for any map is still exponential. The yes-or-no version of the problem (“is there a route shorter than X kilometers?”) is NP-complete, a close relative of the Hamiltonian cycle on Karp’s list. ^[16]

Reductions: a translator between problems

The most important mathematical tool in the field is the reduction. Reducing problem A to problem B means building a fast translator that turns any question about A into a question about B with the same answer. If B is easy, so is A. That is how Karp showed, in 1972, that 21 problems were NP-complete: Karp chained them together, like dominoes, starting from SAT. ^[16]

Why can’t anyone prove it?

It seems it would be enough to prove that some NP-complete problem requires exponential time. But mathematicians found that the known techniques cannot do it. There are at least three proven “barriers”: relativization (1975), natural proofs (1994) and algebrization (2008). Each one shows that a whole kind of argument will never settle the question. ^[4] In other words: solving P versus NP will require inventing new mathematics.

The philosophy

Is creating harder than recognizing?

Think of the difference between composing a song and noticing that it is beautiful, or between inventing a joke and laughing at it. Recognizing seems much easier than creating. P versus NP is the mathematical version of that intuition. Computer scientist Scott Aaronson wrote: ^[1]

“If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in ‘creative leaps,’ no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart.”

Mathematical machines

Gödel had already realized in 1956 that the answer would change the role of mathematicians: if finding proofs were as easy as checking them, a machine could do much of the work. ^[18] Today, AI programs already help find and check proofs, but that does not settle the question: they use shortcuts that work in many cases, not in all.

What counts as knowledge

Aaronson also argues that philosophers should care about complexity. Knowing that an answer exists is not the same as being able to find it in a reasonable time. Every chess position has a perfect move, but no one, and no computer, can always calculate it. For Aaronson, efficiency changes old questions about what it means to know, to learn and even to think. ^[3]

A law of nature?

Some go further and suggest that “NP-complete problems are hard” could be treated as a principle of physics, just like “nothing travels faster than light”. If no system in the universe, not even a quantum one, can solve them quickly, that would say something about nature itself. ^[2]

Looking ahead

What the experts bet on

In 2019, computer scientist William Gasarch repeated a poll of researchers in the field. Of the 124 responses, about 80% said they believe P ≠ NP; among those who have studied the problem most, 99%. And 66% thought the question will be settled before 2100. ^[13]

If P = NP

Lance Fortnow describes this scenario as a world where almost everything could be optimized, from delivery routes to drugs and materials, and where computers would find mathematical proofs on their own. The dark side: the cryptography that protects passwords, banks and messages depends on hard problems and would become vulnerable if the algorithm were practical. ^[11]

If P ≠ NP

This is the most likely scenario. Hard problems stay hard, and that is good for security. To tackle them in practice, we use approximations (a good answer, not a perfect one) and heuristics (shortcuts that work in most cases). That is how delivery apps plan routes every day without waiting millions of years.

What about quantum computers?

They should not change this picture. A quantum computer can factor large numbers very quickly, with Peter Shor’s 1994 algorithm, which threatens part of today’s cryptography. But factoring is not an NP-complete problem, and experts believe that not even quantum computers can solve NP-complete problems quickly. ^[2] As a precaution, NIST published post-quantum cryptography standards in 2024, designed to resist them too. ^[19]

And artificial intelligence?

AI is great at finding good answers to hard problems, such as building school timetables or planning routes, but it does so with heuristics, with no guarantee of always being right. It does not change the class of a problem. One day it may help mathematicians find the proof that P ≠ NP but, given the barriers we saw, that will take a genuinely new idea.

Conclusion

Computational complexity was born from a simple question: how much effort does it take to solve a problem? It showed that there are easy, hard and impossible problems, and that the difference between polynomial and exponential is worth more than any new computer.

P versus NP is at once a question of mathematics, technology and philosophy. The answer could protect or expose our secrets, tell us whether creativity can be automated and reveal limits of nature itself. And it is still waiting for someone to find it. Maybe you?

Essential glossary

Algorithm

A list of steps that solves a problem, like a recipe.

Approximation

An algorithm that gives a good answer, guaranteed to be close to the best, though not necessarily perfect.

EXP

Problems that can be solved in exponential time.

Exponential time

A number of steps that grows like 2ⁿ or n!; it explodes quickly.

Heuristic

A shortcut that usually works well in practice, with no guarantee for every case.

n

The size of the problem: items in a list, cities on a map, squares on a board.

NP

Problems whose answer, once someone shows it, can be checked in polynomial time.

NP-complete

The hardest problems in NP: if one has a fast solution, they all do.

NP-hard

Problems at least as hard as the NP-complete ones, whether or not they are in NP.

P

Problems that can be solved in polynomial time.

Polynomial time

A number of steps that grows like n², n³ or another fixed power of n; considered efficient.

Reduction

A fast translation of one problem into another with the same answer.

SAT

The problem of deciding whether a logical formula can be true; the first known NP-complete problem.

Undecidable

A problem no computer can solve, such as the halting problem.

Quick review

References

1. Aaronson, S., “Reasons to believe”, September 2006, Shtetl-Optimized.
2. Aaronson, S., “NP-complete Problems and Physical Reality”, 2005, scottaaronson.com.
3. Aaronson, S., “Why Philosophers Should Care About Computational Complexity”, August 2011, arXiv:1108.1791.
4. Aaronson, S.; Wigderson, A., “Algebrization: A New Barrier in Complexity Theory”, 2008, scottaaronson.com.
5. Agrawal, M.; Kayal, N.; Saxena, N., “PRIMES is in P”, 2004, Annals of Mathematics 160.
6. Aloupis, G.; Demaine, E. D.; Guo, A.; Viglietta, G., “Classic Nintendo Games are (Computationally) Hard”, 2014, arXiv:1203.1895.
7. Ben-Ari, M., “Minesweeper as an NP-complete problem”, 2005, ACM SIGCSE Bulletin.
8. Clay Mathematics Institute, “P vs NP”, claymath.org.
9. Demaine, E. D.; Hohenberger, S.; Liben-Nowell, D., “Tetris is Hard, Even to Approximate”, 2003, csail.mit.edu.
10. Fortnow, L.; Homer, S., “A Short History of Computational Complexity”, 2003, lance.fortnow.com.
11. Fortnow, L., “The Golden Ticket: P, NP, and the Search for the Impossible”, April 2013, Princeton University Press.
12. Fraenkel, A. S.; Lichtenstein, D., “Computing a perfect strategy for n × n chess requires time exponential in n”, 1981, Journal of Combinatorial Theory A 31.
13. Gasarch, W.; Fortnow, L., “Third Poll on P vs NP and related Questions is out now!”, March 2019, Computational Complexity blog.
14. Hartmanis, J.; Stearns, R. E., “On the computational complexity of algorithms”, 1965, Transactions of the AMS 117.
15. Kendall, G.; Parkes, A.; Spoerer, K., “A Survey of NP-Complete Puzzles”, 2008, ICGA Journal.
16. Wikipedia, “Karp’s 21 NP-complete problems”, en.wikipedia.org.
17. Wikipedia, “Cook–Levin theorem”, en.wikipedia.org.
18. Lipton, R. J., “The Gödel Letter”, rjlipton.com.
19. NIST, “Post-Quantum Cryptography FIPS Approved”, August 2024, csrc.nist.gov.
20. Stanford Encyclopedia of Philosophy, “Turing Machines”, plato.stanford.edu.
21. Walsh, T., “Candy Crush is NP-hard”, March 2014, arXiv:1403.1911.

Origini

Perché un computer risolve alcuni problemi in un batter d’occhio mentre altri richiederebbero più tempo dell’età dell’universo? È la domanda della complessità computazionale, l’area dell’informatica che misura quanto è difficile risolvere un problema.

Prima dei computer: Turing

Nel 1936, prima ancora che esistessero computer come quelli di oggi, il matematico Alan Turing immaginò una macchina semplice, capace di eseguire qualsiasi calcolo passo dopo passo. Con essa dimostrò una cosa sorprendente: esistono problemi che nessun computer potrà mai risolvere. Il più famoso è il problema della fermata: non esiste un programma capace di guardare qualsiasi altro programma e dire, sempre, se terminerà o girerà per sempre. ^[20]

La lettera di Gödel

Il 20 marzo 1956, il logico Kurt Gödel scrisse una lettera al matematico John von Neumann. In essa chiedeva quanto tempo una macchina impiegherebbe a trovare la dimostrazione di un teorema. Se fosse poco, osservava, il lavoro mentale dei matematici sulle domande a risposta sì o no potrebbe essere svolto da macchine. Senza saperlo, Gödel aveva appena posto la domanda che oggi chiamiamo P = NP. ^[18]

L’area riceve un nome

Nel 1965, Juris Hartmanis e Richard Stearns pubblicarono un articolo che misurava il tempo degli algoritmi in funzione della dimensione del problema e diede il nome all’area: complessità computazionale. Il lavoro valse a entrambi il Premio Turing del 1993, il “Nobel dell’informatica”. ^{[14] [10]} Nello stesso periodo, Alan Cobham e Jack Edmonds proposero una regola valida ancora oggi: un algoritmo è efficiente quando il suo tempo cresce come un polinomio, per esempio n² o n³, e non come un’esponenziale, per esempio 2ⁿ. ^[10]

Nasce la domanda da un milione di dollari

Nel 1971, Stephen Cook mostrò che un problema di logica chiamato SAT è NP-completo, cioè uno dei più difficili della classe NP. ^[17] Nel 1972, Richard Karp mostrò che altri 21 problemi famosi erano altrettanto difficili. ^[16] E dall’altra parte della cortina di ferro, in Unione Sovietica, Leonid Levin arrivò alla stessa idea in modo indipendente, pubblicandola nel 1973. ^[17] Nel 2000, l’Istituto Clay ha incluso P contro NP tra i sette Problemi del Millennio, con un premio di 1 milione di dollari per chi lo risolverà. ^[8]

Classificazione

Un algoritmo è una ricetta

Un algoritmo è una ricetta: un elenco di passi che, seguiti alla lettera, risolvono un problema. Per confrontare le ricette, gli scienziati non misurano il tempo con l’orologio, che dipende da ogni computer. Contano quanti passi servono alla ricetta man mano che il problema cresce. La dimensione del problema si chiama n: il numero di elementi di una lista, di città su una mappa o di caselle su una scacchiera.

Veloce e lento: polinomiale contro esponenziale

Immagina un computer che fa 1 miliardo di passi al secondo. Un algoritmo che richiede n² passi risolve un problema con 100 elementi in 10 microsecondi. Un algoritmo che richiede 2ⁿ passi impiegherebbe 40 bilioni di anni per gli stessi 100 elementi, circa 3.000 volte l’età dell’universo. La differenza non sta nel computer: sta nella ricetta.

Per questo la regola di Cobham ed Edmonds è così utile: gli algoritmi polinomiali restano praticabili quando il problema cresce; quelli esponenziali no. Nemmeno i computer più veloci compensano questa esplosione.

P: facile da risolvere

La classe P riunisce i problemi che un computer risolve in tempo polinomiale. Ordinare una lista di nomi, trovare il percorso più breve con il GPS e perfino verificare se un numero enorme è primo stanno in P. Quest’ultimo è stato dimostrato solo nel 2002, da Manindra Agrawal e da due suoi studenti, Neeraj Kayal e Nitin Saxena. ^[5]

NP: facile da verificare

La classe NP riunisce i problemi in cui, se qualcuno ti consegna una risposta, puoi controllare in fretta se è giusta. Il Sudoku è l’esempio perfetto: risolvere una griglia gigante può richiedere tentativi infiniti, ma controllare una griglia già compilata significa solo guardare righe, colonne e quadrati.

Attenzione a una confusione comune: NP non significa “non polinomiale”. Significa “polinomiale non deterministico”, come se il computer potesse indovinare la risposta giusta e dovesse solo controllarla. Ogni problema di P sta anche in NP: chi sa risolvere in fretta sa anche controllare in fretta.

NP-completo e NP-difficile

Dentro NP ci sono i problemi più difficili di tutti, gli NP-completi. Hanno una proprietà magica: se qualcuno scopre un modo rapido per risolverne uno, tutti i problemi di NP diventano risolvibili rapidamente. I problemi NP-difficili, invece, sono almeno difficili quanto gli NP-completi, ma non devono per forza stare in NP: alcuni non hanno nemmeno una risposta sì o no, e altri, come il problema della fermata, non si possono proprio risolvere.

Oltre NP

Alcuni problemi sono dimostrabilmente ancora più difficili. Trovare la mossa perfetta negli scacchi giocati su una scacchiera n × n, che può crescere a piacere, richiede tempo esponenziale: quel problema sta nella classe EXP. ^[12] E oltre tutto ci sono gli indecidibili, come il problema della fermata di Turing.

I tuoi giochi preferiti sono difficili

Gli scienziati adorano dimostrare che i giochi sono difficili. Ecco alcuni risultati:

In tutti i casi, i risultati valgono per versioni generalizzate, con griglie o livelli di qualsiasi dimensione. Un normale Sudoku 9 × 9 un computer lo risolve in un istante.

• “NP significa non polinomiale”

  Realtà: NP significa polinomiale non deterministico, cioè facile da verificare.

• “NP-difficile significa impossibile”

  Realtà: significa che non si conosce una scorciatoia rapida per tutti i casi. I casi piccoli o comuni spesso si risolvono bene.

• “Un computer più veloce lo risolve”

  Realtà: contro una crescita esponenziale, raddoppiare la velocità non cambia quasi nulla.

• “Il computer quantistico risolve tutto”

  Realtà: gli esperti ritengono che nemmeno lui risolva rapidamente i problemi NP-completi. ^[2]

La matematica

Polinomi contro esponenziali

Tutta la teoria si basa sul confronto tra due tipi di funzione. In un polinomio, n sta alla base e l’esponente è fisso; in un’esponenziale, n passa all’esponente:

Polinomiale:   n²   n³   n¹⁰    → l’esponente è fisso
Esponenziale:  2ⁿ   3ⁿ   n!     → n sta all’esponente (o nel fattoriale)

n = 10:   n² = 100     2ⁿ = 1.024            n! = 3.628.800
n = 30:   n² = 900     2ⁿ = 1.073.741.824    n! ≈ 2,7 × 10³²

Per quanto grande sia l’esponente di un polinomio, un’esponenziale finisce sempre per superarlo. Per questo il confine tra P e il resto è così importante.

Il commesso viaggiatore

Un esempio classico: un corriere deve visitare diverse città e tornare al punto di partenza con il percorso più breve. Con n città esistono (n − 1)! ÷ 2 percorsi diversi. Con 5 città sono 12. Con 25 sono oltre 3 × 10²³: provarli tutti richiederebbe circa 10 milioni di anni.

Esistono algoritmi più furbi, che evitano di provare tutto, ma tutti quelli conosciuti che danno la risposta esatta per qualsiasi mappa restano esponenziali. La versione sì o no del problema (“esiste un percorso più corto di X chilometri?”) è NP-completa, parente stretta del ciclo hamiltoniano della lista di Karp. ^[16]

Riduzioni: un traduttore tra problemi

Lo strumento matematico più importante dell’area è la riduzione. Ridurre il problema A al problema B significa costruire un traduttore rapido che trasforma qualsiasi domanda di A in una domanda di B con la stessa risposta. Se B è facile, lo è anche A. È così che Karp mostrò, nel 1972, che 21 problemi erano NP-completi: li collegò a catena, come tessere del domino, partendo da SAT. ^[16]

Perché nessuno riesce a dimostrarlo?

Sembrerebbe bastare dimostrare che un problema NP-completo richiede tempo esponenziale. Ma i matematici hanno scoperto che le tecniche conosciute non ci riescono. Esistono almeno tre “barriere” dimostrate: la relativizzazione (1975), le dimostrazioni naturali (1994) e l’algebrizzazione (2008). Ognuna mostra che un intero tipo di argomento non risolverà mai la questione. ^[4] In altre parole: per risolvere P contro NP bisognerà inventare matematica nuova.

La filosofia

Creare è più difficile che riconoscere?

Pensa alla differenza tra comporre una canzone e accorgersi che è bella, o tra inventare una barzelletta e riderne. Riconoscere sembra molto più facile che creare. P contro NP è la versione matematica di questa intuizione. L’informatico Scott Aaronson ha scritto: ^[1]

“Se P = NP, il mondo sarebbe un luogo profondamente diverso da come di solito lo immaginiamo. Non ci sarebbe alcun valore speciale nei ‘salti creativi’, nessuna differenza fondamentale tra risolvere un problema e riconoscere la soluzione una volta trovata. Chiunque sapesse apprezzare una sinfonia sarebbe Mozart.”

Macchine matematiche

Gödel aveva già capito nel 1956 che la risposta avrebbe cambiato il ruolo dei matematici: se trovare dimostrazioni fosse facile quanto controllarle, una macchina potrebbe fare gran parte del lavoro. ^[18] Oggi i programmi di IA aiutano già a trovare e controllare dimostrazioni, ma questo non risolve la questione: usano scorciatoie che funzionano in molti casi, non in tutti.

Che cosa conta come conoscenza

Aaronson sostiene anche che i filosofi dovrebbero interessarsi alla complessità. Sapere che una risposta esiste non è la stessa cosa che riuscire a trovarla in un tempo ragionevole. Ogni posizione degli scacchi ha una mossa perfetta, ma nessuno, e nessun computer, riesce sempre a calcolarla. Per Aaronson, l’efficienza cambia antiche domande su che cosa significhi conoscere, imparare e perfino pensare. ^[3]

Una legge di natura?

C’è chi va oltre e suggerisce che “i problemi NP-completi sono difficili” potrebbe essere trattato come un principio della fisica, proprio come “niente viaggia più veloce della luce”. Se nessun sistema dell’universo, nemmeno quantistico, riesce a risolverli rapidamente, questo direbbe qualcosa sulla natura stessa. ^[2]

Uno sguardo al futuro

Su cosa scommettono gli esperti

Nel 2019, l’informatico William Gasarch ha ripetuto un sondaggio tra i ricercatori dell’area. Su 124 risposte, circa l’80% ha detto di credere che P ≠ NP; tra chi ha studiato di più il problema, il 99%. E il 66% pensa che la questione sarà risolta prima del 2100. ^[13]

Se P = NP

Lance Fortnow descrive questo scenario come un mondo in cui quasi tutto potrebbe essere ottimizzato, dai percorsi di consegna ai farmaci e ai materiali, e in cui i computer troverebbero da soli le dimostrazioni matematiche. Il lato oscuro: la crittografia che protegge password, banche e messaggi dipende da problemi difficili e diventerebbe vulnerabile se l’algoritmo fosse pratico. ^[11]

Se P ≠ NP

È lo scenario più probabile. I problemi difficili restano difficili, e questo è un bene per la sicurezza. Per affrontarli nella pratica usiamo approssimazioni (una risposta buona, non perfetta) ed euristiche (scorciatoie che funzionano nella maggior parte dei casi). È così che le app di consegna pianificano i percorsi ogni giorno senza aspettare milioni di anni.

E i computer quantistici?

Non dovrebbero cambiare questo quadro. Un computer quantistico può fattorizzare numeri grandi molto in fretta, con l’algoritmo di Peter Shor del 1994, il che minaccia parte della crittografia di oggi. Ma fattorizzare non è un problema NP-completo, e gli esperti ritengono che nemmeno i computer quantistici risolvano rapidamente i problemi NP-completi. ^[2] Per precauzione, nel 2024 il NIST ha pubblicato standard di crittografia post-quantistica, pensati per resistere anche a loro. ^[19]

E l’intelligenza artificiale?

L’IA è bravissima a trovare buone risposte a problemi difficili, come comporre orari scolastici o pianificare percorsi, ma lo fa con euristiche, senza garanzia di azzeccare sempre. Non cambia la classe di un problema. Forse un giorno aiuterà i matematici a trovare la dimostrazione che P ≠ NP ma, viste le barriere, servirà un’idea davvero nuova.

Conclusione

La complessità computazionale è nata da una domanda semplice: quanto sforzo serve per risolvere un problema? Ha mostrato che esistono problemi facili, difficili e impossibili, e che la differenza tra polinomiale ed esponenziale vale più di qualsiasi nuovo computer.

P contro NP è allo stesso tempo una questione di matematica, di tecnologia e di filosofia. La risposta potrebbe proteggere o esporre i nostri segreti, dirci se la creatività si può automatizzare e rivelare limiti della natura stessa. E sta ancora aspettando qualcuno che la trovi. Magari tu?

Glossario essenziale

Algoritmo

Elenco di passi che risolve un problema, come una ricetta.

Approssimazione

Algoritmo che dà una risposta buona, garantita vicina alla migliore, ma non necessariamente perfetta.

Euristica

Scorciatoia che di solito funziona bene nella pratica, senza garanzia per tutti i casi.

EXP

Problemi che possono essere risolti in tempo esponenziale.

Indecidibile

Problema che nessun computer può risolvere, come il problema della fermata.

n

La dimensione del problema: elementi di una lista, città di una mappa, caselle di una scacchiera.

NP

Problemi la cui risposta, quando qualcuno la mostra, può essere verificata in tempo polinomiale.

NP-completo

I problemi più difficili di NP: se uno ha una soluzione rapida, ce l’hanno tutti.

NP-difficile

Problemi almeno difficili quanto gli NP-completi, che stiano o no in NP.

P

Problemi che possono essere risolti in tempo polinomiale.

Riduzione

Traduzione rapida di un problema in un altro, con la stessa risposta.

SAT

Problema di decidere se una formula logica può essere vera; il primo problema NP-completo conosciuto.

Tempo esponenziale

Numero di passi che cresce come 2ⁿ o n!; esplode rapidamente.

Tempo polinomiale

Numero di passi che cresce come n², n³ o un’altra potenza fissa di n; considerato efficiente.

Ripasso veloce

Riferimenti

1. Aaronson, S., “Reasons to believe”, settembre 2006, Shtetl-Optimized.
2. Aaronson, S., “NP-complete Problems and Physical Reality”, 2005, scottaaronson.com.
3. Aaronson, S., “Why Philosophers Should Care About Computational Complexity”, agosto 2011, arXiv:1108.1791.
4. Aaronson, S.; Wigderson, A., “Algebrization: A New Barrier in Complexity Theory”, 2008, scottaaronson.com.
5. Agrawal, M.; Kayal, N.; Saxena, N., “PRIMES is in P”, 2004, Annals of Mathematics 160.
6. Aloupis, G.; Demaine, E. D.; Guo, A.; Viglietta, G., “Classic Nintendo Games are (Computationally) Hard”, 2014, arXiv:1203.1895.
7. Ben-Ari, M., “Minesweeper as an NP-complete problem”, 2005, ACM SIGCSE Bulletin.
8. Clay Mathematics Institute, “P vs NP”, claymath.org.
9. Demaine, E. D.; Hohenberger, S.; Liben-Nowell, D., “Tetris is Hard, Even to Approximate”, 2003, csail.mit.edu.
10. Fortnow, L.; Homer, S., “A Short History of Computational Complexity”, 2003, lance.fortnow.com.
11. Fortnow, L., “The Golden Ticket: P, NP, and the Search for the Impossible”, aprile 2013, Princeton University Press.
12. Fraenkel, A. S.; Lichtenstein, D., “Computing a perfect strategy for n × n chess requires time exponential in n”, 1981, Journal of Combinatorial Theory A 31.
13. Gasarch, W.; Fortnow, L., “Third Poll on P vs NP and related Questions is out now!”, marzo 2019, Computational Complexity blog.
14. Hartmanis, J.; Stearns, R. E., “On the computational complexity of algorithms”, 1965, Transactions of the AMS 117.
15. Kendall, G.; Parkes, A.; Spoerer, K., “A Survey of NP-Complete Puzzles”, 2008, ICGA Journal.
16. Wikipedia, “Karp’s 21 NP-complete problems”, en.wikipedia.org.
17. Wikipedia, “Cook–Levin theorem”, en.wikipedia.org.
18. Lipton, R. J., “The Gödel Letter”, rjlipton.com.
19. NIST, “Post-Quantum Cryptography FIPS Approved”, agosto 2024, csrc.nist.gov.
20. Stanford Encyclopedia of Philosophy, “Turing Machines”, plato.stanford.edu.
21. Walsh, T., “Candy Crush is NP-hard”, marzo 2014, arXiv:1403.1911.