• Tweet
• 

O que é mais fácil: resolver um problema de matemática ou verificar a resposta ao mesmo problema feito por outra pessoa? Uma resposta para esta questão – acompanhada de uma demonstração e valendo para todos os problemas “fáceis” – vale um milhão de dólares e pode ter impactos vastos sobre a cultura.

Primeiro um parágrafo complicado para tentar explicar o problema. Se é que eu o entendi.

O problema é:

Verificar se tudo que é facilmente verificável seria também facilmente solucionável.

Para nós, em geral encontrar o resultado da multiplicação 17 x 9 é mais fácil do que encontrar dois fatores que dêem 91: ? x ? = 91. Os problemas em computação podem ser divididos pelo número de passos que levam para ser calculados — essa é uma medida de sua relativa facilidade e do tempo verdadeiro que levarão para serem realizados.

Existem formas de medir a relação entre o número de passos de um problema e seu resultado. Para nossos fins, se o problema tem uma relação pequena entre os passos e o resultado, determinada por um critério matemático, se chama esse problema de P.

Por exemplo, a relação não deve ser exponencial: caso em que a cada entrada adicional o número de passos aumenta muito. Estamos falando de problemas “simples” dessa forma. NP seria partir do resultado e verificar o problema.

A questão de US$ 1.000.000 é obter a prova de se tudo que é NP (facilmente verificável) seria também P (facilmente solucionável), ou uma prova de que eles sempre são diferentes, ou até mesmo uma prova de que é impossível obter tal prova.

Esse cara ganhou U$ 1.000.000 por resolver um problema matemático de 99 anos de idade. Recusou o dinheiro porque sente que a matemática lhe dá “controle sobre o universo”. (Clique para ler matéria em inglês sobre isso)

OK, e daí?

Agora veja as áreas onde uma prova com qualquer dos dois resultados (e mesmo se ficar provado que ele não pode ser provado) será extremamente importante:

• lógica,
• matemática,
• ciência da computação,
• criptografia,
• inteligência artificial,
• teoria dos jogos,
• processamento de multimídia.

Há muitas outras. Daí ele ser um dos Millennium Prize Problems, com um prêmio de 1.000.000 de dólares, oferecido pelo Instituto Clay de Matemática, em Cambridge, Massachusetts.

Também está para sair um filme sobre o problema, chamado Travelling Salesman.

Link YouTube

Não sei exatamente que tipo de resultados qualquer uma dessas três soluções (que todo NP é P, ou que não é, ou que seja impossível provar) teria sobre teoria dos jogos ou inteligência artificial – embora qualquer uma das duas áreas seja fértil para vastos impactos sociais e culturais.

Teoria dos Jogos pode afetar organizações, processos eleitorais, e até mesmo coisas como o próprio capitalismo.

Inteligência artificial, dependendo de que tipo e com que intensidade, pode também transformar tudo, como explorado na ficção científica. (Podemos até misturar os dois e pegar um computador revolucionário, como o do livro de Robert Heinlein, The Moon is a Harsh Mistress, “Revolta na Lua”, 1967).

Nosso mundo encriptado

Mas fiquemos com a criptografia. Se NP for, por acaso, igual a P, tudo que hoje depende de criptografia vai ficar enfraquecido – já que, embora os algorítimos não tenham sido encontrados para violar todo tipo de criptografia, estará provado que qualquer criptografia pode ser violada com a descoberta de um algorítmo.

Por outro lado, é mais provável que NP seja provado diferente de P, nesse caso poderemos confiar cada vez mais na criptografia: e isso tem boas e más implicações.

Atualmente a criptografia é, por um lado, uma das questões mais importantes para as liberdades civis, e por outro assustadoramente perigosa. Vivemos à beira de uma criptoanarquia. Em redes obscuras (darknets) tais como TOR , pedofilia, drogas e até assassinatos são comercializados em bitcoin.

A comunicação é criptografada, impossível de rastrear, e a própria moeda é baseada na criptografia! Dependendo do resultado, um matemático que faça essa prova talvez ganhasse mais de um milhão ao especular no mercado de bitcoin: caso prove-se que N é diferente de NP, o valor da bitcoin naturalmente subirá.

Por outro lado, é a criptografia que garante também nossas relações comerciais cotidianas pela internet, e que garante alguma privacidade em todas as comunicações eletrônicas que fazemos. O governo britânico já baixou uma lei, extremamente problemática do ponto de vista das liberdades civis, que garante o aprisionamento de alguém com um arquivo criptografado – contenha o que ele contiver.

Rickard Falkvinge, atualmente o maior ativista na área de liberdades civis e computadores, afirma que qualquer arquivo relativamente aleatório, tal como uma foto em modo RAW, pode despertar suspeitas. Por outro lado, os arquivos criptografados são facilmente ocultáveis em meio a arquivos comuns, de forma que a lei britânica não faz muito sentido.

Essa mudança ocorreu muito rápido devido ao também rápido crescimento do poder de processamento das máquinas caseiras. Certos graus de encriptação só disponíveis aos militares 20 anos atrás, e até proibidos ao público em geral, se tornaram disponíveis e rápidos nos computadores atuais.

Excetuando tortura e outros métodos de extração de uma senha, certos padrões de encriptação comuns em máquinas caseiras são virtualmente invioláveis em tempo hábil com o poder de computação dos maiores supercomputadores disponíveis.

Em outras palavras, é um Admirável Mundo Novo de criptografia, por um lado assustador, por outro maravilhoso em reduzir a assimetria entre grandes potências (e como a Alemanha apanhou por causa da criptografia, aparentemente excelente, na Segunda Guerra, não é mesmo? E o quanto isso desenvolveu a própria existência do computador!) e um cidadão comum. Como cobrar impostos sobre o bitcoin, se nem mesmo transações ilegais podem ser investigadas? O paraíso fiscal está dentro do processador, junto com o caixa 2.

Portanto, é possível que vejamos cada vez mais ataques contra a liberdade civil em geral para nos proteger dos pedófilos e terroristas que se utilizam dessas tecnologias. Precisamos ter muito cuidado com isso: 11 de Setembro destruiu muitas das liberdades civis de que os próprios americanos tinham orgulho – em nome da proteção e da defesa, eles começaram a invadir a privacidade do próprio povo, em grau nunca visto.

Independente do resultado da questão P vs NP, que pode levar muito séculos para acontecer (ou não acontecer nunca), precisamos seguir atentos a que tipo de transformações sociais e culturais – que políticas vão tentar ser aplicadas – para afetar nosso cotidiano em nome de certas questões aparentemente tão abstratas.

Cada vez mais é necessário refletir sobre a interconexão e a complexidade de problemas que nunca estão longe demais de todos nós.

*   *   *

Na coluna “WTF”, Eduardo Pinheiro tem total liberdade para nos ajudar a ver o que precisa ser visto.

“WTF” no sentido do espanto que dá origem à filosofia, à ciência, às tradições de sabedoria. E WTF no sentido do impacto que isso talvez nos cause, quebrando cegueiras, ilusões.

Além de seguir o papo abaixo nos comentários, você pode enviar suas mais profundas perguntas para wtf@papodehomem.com.br .