Alemão diz ter resolvido um dos maiores problemas da ciência da computação

Este artigo foi publicado originalmente no Motherboard Alemanha. O que é que a cura para o câncer, o capitalismo justo e um jogo perfeito de Super Mario Bros. têm em comum? Por meio de uma teoria matemática, a solução desses problemas nos permitiria resolver rapidamente todos os demais. Tudo o que precisamos são algoritmos muito bons para perguntas complicadas – como o enovelamento de proteínas, mercados eficientes e análises combinatórias – que são meras variações de problemas simples cujos supercomputadores ainda estão por resolver.

Mas como é possível que um algoritmo simplifique problemas extremamente complicados? Isso depende de outra pergunta: e se esses problemas complicados não passam de problemas simples disfarçados? O desafio é uma das maiores questões não resolvidas pela matemática moderna e se trata de uma das sete perguntas do Prêmio Millennium, que premia cada resposta aceita com um milhão de dólares.

Agora, um alemão chamado Norbert Blum alegou ter resolvido o desafio, que é conhecido como o problema P versus NP. Infelizmente, a solução apresentada não traz boas notícias. Blum, da Universidade de Bonn, na Alemanha, afirma em seu artigo de 38 páginas recém-publicado que P não é igual a NP. Em outras palavras, os problemas complicados são fundamentalmente diferentes dos problemas simples e objetivos, e não é possível que nossos computadores de alto desempenho sejam capazes de resolver essas questões de grande complexidade um dia. Desde que seu artigo foi publicado, muitos matemáticos começaram a questionar se, assim, Blum realmente resolveu a pergunta.

A maioria dos cientistas da computação tende a concordar com a conclusão de Blum. Problemas difíceis são complicados, e problemas fáceis são… Mais simples.

Nas ciências da computação, problemas fáceis costumam estar sob a forma de P. Isso significa que eles podem ser resolvidos em um "tempo polinomial". É praticamente como dizer que eles podem ser resolvidos em um período de tempo razoável. Os problemas muito mais complicados são os NP, incapazes de resolver por um computador em um período de tempo razoável. Por razões práticas, os problemas NP podem até nem ser resolvidos por computadores. (Observação: entretanto, o NP significa "tempo polinomial não determinístico" em vez de tempo "não polinomial".)

Seguem alguns exemplos de problemas NP:

Envelopamento de proteínas: é o processo pelo qual proteínas em um organismo biológico obtêm sua estrutura. Uma compreensão melhor desse processo poderia ajudar no reconhecimento das mutações, ou mesmo impedi-las, possibilitando a cura de certas formas de câncer.

Otimizar percursos: uma viagem com o melhor percurso possível através de 15 cidades diferentes sem passar pela mesma cidade duas vezes? Problema difícil de resolver, mesmo para um computador, por isso que na ciência da computação é considerado um problema NP.

A partida de xadrez perfeita: uma partida de xadrez têm infinitas possibilidades de movimentos, tanto que mesmo um supercomputador com capacidade extraordinária não é capaz de determinar uma tática perfeita. Muitos matemáticos consideram esse problema tão difícil que nem o consideram problema NP, mas o colocam completamente fora do âmbito de possibilidades.

Todos esses problemas complexos têm algo em comum: por mais difícil que seja encontrar uma solução para os problemas NP, é relativamente fácil verificar a validade das soluções propostas a elas.

Essas duas distinções categóricas na complexidade dos problemas têm suas origens muito antes da popularização dos computadores pessoais. Nos anos 1970, quando os computadores ainda tinham o tamanho de um refrigerador, determinou-se rapidamente que nem todos os problemas da humanidade poderiam ser simplesmente resolvidos por essas máquinas. Propôs-se que a distinção poderia ser formalizada em termos de complexidade computacional, levando à organização de classes de complexidade, incluindo a N e NP.

Desde a definição formal de P e NP em 1971, cientistas da computação debateram a possibilidade ou não de haver um algoritmo capaz de reduzir ou redefinir problemas NP de forma que pudessem ser resolvidos em tempo polinomial. Se alguém conseguisse provar que todos os problemas NP são, no fim das contas, variações de problemas P, então todos os problemas NP estariam, em essência, sujeitos ao mesmo tipo de redução. Em outras palavras, aquele ou aquela que conhecer a melhor tática para o Super Mario Bros. também poderá curar o câncer.

No total, 116 pessoas corajosas em suas áreas tentaram oficialmente resolver o mistério (sem contar que muitos cientistas da computação postaram possíveis soluções em mensagens e comentários de sites como o arXiv). Até o momento, nenhuma dessas resoluções foi reconhecida oficialmente pela comunidade matemática.

Em 2000, o Instituto de Matemática Clay (CMI), localizado em Oxford, compilou uma lista de sete problemas do prêmio Millennium os quais não foram resolvidos, oferecendo um milhão de dólares para cada solução. É tipo um Quem Quer Ser Milionário? dos matemáticos.

Os problemas do Millennium são considerados excepcionalmente difíceis, mesmo entre os círculos de especialistas. Uma grande quantidade de conhecimento específico da área é necessária somente para compreender as perguntas. O único problema resolvido até agora foi a Conjectura de Poincaré, que não pode ser facilmente explicada em um artigo sobre um conceito matemático diferente.

Resolver o problema NP pode não ser algo bom. Por exemplo, a maior parte da criptografia é baseada na dificuldade de fatoração de números primos muito grandes. A fatoração de inteiros é uma classe de problema NP. Um código de 256 bits, como o que as instituições financeiras utilizam em pagamentos com o cartão de crédito, é considerado inquebrável, logo, muito seguro. Se alguém provar que NP é igual a P, então os bancos precisarão se mexer para encontrar rapidamente outro método de segurança.

Desde que o artigo de Blum foi publicado, matemáticos e cientistas da computação em todo o mundo começaram a quebrar a cabeça e discutir se o pesquisador de Bonn, de fato, resolveu o problema do prêmio Millennium. Após uma primeira reação positiva, como a do matemático de Stanford Reza Zadeg, as dúvidas estão começando aparecer sobre o raciocínio de Blum.

Em um fórum de matemáticos teóricos, um usuário chamado Mikhail contatou Alexander Razborov – autor do artigo em que Blum se baseia – para questioná-lo a respeito do texto de Blum. Razbotov alega ter descoberto um erro na premissa principal de Blum, que contradiz uma das principais hipóteses de Razborov. E o matemático Scott Aaronson, uma espécie de autoridade da comunidade matemática no que diz respeito ao P versus NP, afirmou que está disposto a apostar 200 mil dólares em que a prova matemática de Blum não se sustentará.

"Parem de me perguntar", Aaronson escreveu, sobre se a prova já fora refutada, "vocês podem voltar mais tarde e mostrar que eu fui um trouxa teimoso".

Na semana em que Aaronson publicou o post, outros matemáticos começaram a tentar encontrar furos na prova de Blum. Dick Lipton, professor de ciência da computação na Georgia Tech, escreveu em um post que a prova de Blum "tem muitas camadas de seriedade", mas sugere que pode haver alguns problemas nela. Um comentário do mesmo post, feito por alguém identificado somente como "vloodin", observou que há um "único erro, em um ponto sutil" da prova; outros matemáticos fizeram eco e confirmaram a análise inicial de "vloodin". Até o momento, o consenso entre muitos matemáticos é que a solução para o problema P versus NP permanece indefinida.

Traduzido para o inglês por Melina McCormack.

Leia mais matérias de ciência e tecnologia no canal MOTHERBOARD.
Siga o Motherboard Brasil no Facebook e no Twitter.
Siga a VICE Brasil no Facebook , Twitter e Instagram .