Imagine um tabuleiro de xadrez. Coloque duas rainhas rivais nele, de modo que não possam se atacar diretamente. Fácil? Bem, agora repita o processo adicionando mais seis rainhas. Complicado, mas possível. Para finalizar, estenda o problema para tabuleiros de qualquer tamanho, com qualquer número de rainhas pré-estabelecidas. O chamado «problema das 1000 rainhas» não é nada além de um exemplo isolado para explicar um exercício muito mais complexo, «P versus NP», a tal ponto que o Instituto Clay de Matemática oferece um milhão de dólares pela primeira demonstração positiva.
Os Sete Problemas do Milênio
Existe uma competição muito interessante chamada «Os Sete Problemas do Milênio». Iniciada no ano 2000 pelo Instituto Clay de Matemática, seu objetivo é encontrar respostas para sete problemas clássicos que têm «resistido» a uma solução ao longo dos anos. Até agora, o único problema que recebeu uma demonstração apropriada é a «Conjectura de Poincaré», desenvolvida pelo matemático russo Grigori Perelman.
O instituto não hesitou em oferecer-lhe um milhão de dólares pelo seu trabalho, mas Perelman o recusou, dizendo que sua contribuição não havia sido maior do que a do matemático Richard S. Hamilton, que havia sugerido uma solução anteriormente. Outro dos grandes problemas que o instituto deseja ver resolvido é o famoso «P versus NP», e para tentar entendê-lo, o mais comum é recorrer ao xadrez:
O que são problemas P e NP?
Não ajudou? Não se preocupe, a mim também não serviu de muito no início. P versus NP é mais complicado do que jogar um par de rainhas sobre um tabuleiro, e sua reputação de impossível é bem justificada. Em termos bem relaxados (e digo «relaxados» com toda sinceridade) podemos dizer que os problemas denominados P são fáceis de resolver e verificar com algoritmos, dentro de um «tempo polinomial».
Por outro lado, os problemas NP são fáceis de verificar se a solução está correta ou não, enquanto chegar a ela demanda muito tempo e esforço, com perdas notáveis de eficiência. Exemplos robustos de problemas NP são quebra-cabeças, Sudoku, e até o Buscaminas. Agora: o que aconteceria se você encontrasse a chave para solucionar um problema NP em tempo polinomial, com grande eficiência?
Se você conseguir isso, comprovará que não há diferenças entre N e NP (N = NP), fazendo com que o Instituto Clay (e não a Universidade de St. Andrews como se tem repetido até a exaustão) lance um milhão de dólares na sua direção, seguido provavelmente por um prêmio Nobel, e o ódio de especialistas em criptografia ao redor do mundo. A maioria dos especialistas se inclina a favor de N ≠ NP, e, para dizer a verdade, muitas coisas dependem disso (o ciframento mencionado anteriormente é uma). Mas se você vai tentar mesmo assim... boa sorte. Você vai precisar.
