Oferecido por
1.Em uma segunda-feira, 19 de julho de 2021, no meio de outro estranho verão pandêmico, um importante cientista da computação no campo da teoria da complexidade computacional escreveu em seu Twitter uma mensagem pública sobre uma confusão administrativa em uma revista. Ele se despediu com um muito carregado:
“Feliz segunda-feira.”
Em um universo paralelo, poderia ter sido uma segunda-feira muito feliz de fato. Mas na conceituada revista online ACM Transactions on Computational Theory apareceu “uma pesquisa excepcionalmente original explorando os limites da computação viável”. O resultado pretendia resolver o problema de todos os problemas: o Santo Graal da teoria computacional, valendo um prêmio de um milhão de dólares e uma fama que rivaliza eternamente com a de Aristóteles.
Este valioso problema, conhecido como “P versus NP”, é considerado ao mesmo tempo o mais importante em ciência da computação teórica e matemática e completamente intangível. Ele aborda questões fundamentais sobre a promessa, limites e ambições da computação, colocando as seguintes questões:
Por que alguns problemas são mais difíceis do que outros?
Quais problemas os computadores podem resolver de forma realista?
Quanto tempo vai demorar?
É uma busca com grandes benefícios filosóficos e práticos.
“Olha, sobre essa pergunta “P versus NP”, o que posso dizer?” Scott Aaronson, cientista da computação da Universidade do Texas em Austin, escreveu em seu livro, Quantum Computing Since Democritus. “As pessoas gostam de descrevê-lo como ‘provavelmente o principal problema não resolvido da ciência da computação teórica’. Isso é um eufemismo cômico. O problema “P vs NP” é uma das perguntas mais profundas que os seres humanos já fizeram”.
Uma maneira de pensar nos protagonistas desta história é a seguinte:
“P” representa problemas que um computador pode resolver com facilidade.
“NP” representa problemas que, uma vez resolvidos, são fáceis de verificar, como um quebra-cabeças ou Sudoku. Muitos problemas do NP correspondem a alguns dos problemas mais persistentes e urgentes que a sociedade enfrenta.
A pergunta de um milhão de dólares que surge com o “P versus NP” é: eles são o mesmo tipo de problema? Ou seja, problemas que parecem tão difíceis podem ser resolvidos com um algoritmo em um período de tempo razoável, se apenas esse algoritmo adequado e incrivelmente rápido pudesse ser encontrado? Se assim fosse, muitos problemas complicados subitamente teriam soluções. E suas soluções algorítmicas podem trazer mudanças sociais de proporções utópicas, em medicina, engenharia, economia, biologia, ecologia, neurociência, ciências sociais, indústria, artes, até política e além.
Às vezes, as classificações evoluem, problemas difíceis se tornam fáceis quando os pesquisadores encontram soluções mais eficientes. Testar se um número é primo, por exemplo, é conhecido por estar na classe NP desde meados da década de 1970. Mas em 2002, três cientistas da computação do Instituto Indiano de Tecnologia Kanpur, na Índia, desenvolveram uma prova incondicional e um algoritmo inteligente que finalmente confirmou que o problema também estava na classe P.
Se todos os problemas complicados pudessem ser transformados com esse truque algorítmico, as consequências para a sociedade, para a humanidade e nosso planeta, seriam enormes.
Para começar, os sistemas de criptografia, a maioria dos quais são baseados em problemas NP, seriam quebrados. Precisaríamos encontrar uma abordagem completamente diferente para enviar comunicações seguras. O dobramento de proteínas, um grande desafio de 50 anos na biologia, se tornaria mais simples, desbloqueando novas habilidades para projetar medicamentos que curam ou tratam doenças e descobrir enzimas que decompõem resíduos industriais. Também significaria encontrar soluções ideais para problemas difíceis do dia a dia, como planejar uma viagem para chegar a todos os destinos dirigindo um mínimo de horas possíveis ou acomodar convidados de casamento para que apenas amigos compartilhem a mesma mesa de jantar.
Desde o início do problema “P versus NP” há 50 anos, que emergiu da importante interseção da lógica matemática e da tecnologia de computação, pesquisadores de todo o mundo fizeram tentativas hercúleas em busca de uma solução. Alguns cientistas da computação sugeriram que os esforços podem ser mais parecidos com os de Sísifo, que sempre trabalhou sem sucesso. Mas enquanto aqueles que começaram a explorar o problema pela primeira vez estão ficando sem tempo para ver uma solução, as novas gerações estão felizes em assumir a busca.
Para Manuel Sabin, um cientista da computação que acaba de terminar um doutorado na UC Berkeley (EUA), o fascínio está em sondar a impossibilidade de problemas em que “você não saberá a resposta até que o sol engula a terra”. A busca pode ser quixotesca, mas Sabin se arrependeria de não lutar contra esses moinhos de vento.
Timothy Gowers, matemático da Universidade de Cambridge, no Reino Unido, o define como um de seus “distúrbios matemáticos pessoais”. Ele passou todo o verão de 2013 estudando isso, depois de pedir a seus alunos uma redação sobre o assunto em uma prova. Como ele relatou em seu blog: “Depois de corrigir as redações em junho, pensei que passaria uma ou duas horas contemplando o problema de novo, até que essa uma ou duas horas, inesperadamente, se transformaram em cerca de três meses”.
A missão do problema “P versus NP” até surpreendeu o cientista da computação da Universidade de Toronto, no Canadá, Stephen Cook, que formulou o problema e lançou o campo da complexidade computacional com um artigo seminal publicado em 1971. Por esse trabalho, ele ganhou o Prêmio Turing, o equivalente em ciência da computação ao Prêmio Nobel. Mas ele não teve sorte em encontrar uma solução. Cook diz que nunca teve boas ideias, “é muito difícil”.
2. Michael Sipser, um cientista da computação do MIT, estima que gastou, ao todo, até uma década no problema. Ele se interessou durante a pós-graduação na década de 1970 e apostou com seu colega Len Adleman um grama de ouro que seria resolvido até o final do século (Sipser perdeu a aposta e teve que pagar).
Na década de 1980, ele alcançou um bom resultado ao resolver uma versão do problema com um modelo computacional “limitado”, o que levou a um período emocionante do campo com vários resultados maravilhosos, criando esperança de que a solução não estivesse muito distante.
Sipser ainda volta ao problema de vez em quando, e é um de seus grandes embaixadores inabaláveis, dando inúmeras palestras sobre o assunto.
A maneira como ele se aproxima de uma explicação acessível de “P versus NP” é com um problema básico de multiplicação: 7 × 13 =?
A resposta, 91, é fácil de calcular em sua cabeça. Embora a multiplicação de números maiores não seja tão fácil, um computador praticamente não demoraria para realizar tal cálculo.
Mas outra coisa é reverter esses problemas. Por exemplo, tente encontrar os dois números primos de 97 dígitos que são multiplicados para dar esse número grande:
310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609
Esse problema de fatoração foi parte de um desafio que testou a dificuldade de quebrar chaves RSA usadas em criptografia. Para resolvê-lo, foram necessários 80 processadores e cinco meses de computação contínua, explica Sipser, o que equivale a aproximadamente 33 anos com apenas um único processador. A fatoração é um problema difícil porque todos os métodos atuais buscam a resposta via “força bruta”, verificando o número astronômico de possibilidades uma a uma. Mesmo para um computador, este é um processo lento.
“A questão interessante aqui é: você realmente precisa pesquisar?”, diz Sipser. “Ou existe alguma maneira de resolver o problema de fatoração que amplie a resposta rapidamente sem pesquisar? Não sabemos a resposta para essa pergunta”.
Perguntas como essas vão ao cerne da complexidade computacional, um campo cheio de problemas bestiais que os pesquisadores estão tentando entender. Aaronson montou um “Zoológico da Complexidade”, um catálogo online com 545 tipos de problemas (e contando). Cada um é classificado de acordo com sua complexidade ou dificuldade computacional e os recursos (tempo, memória, energia) necessários para encontrar as soluções. P e NP são as principais atrações.
Em um acaso científico, um matemático soviético, Leonid Levin, convergiu para um resultado equivalente ao de Cook mais ou menos na mesma época.
P é “a classe que começou tudo”. É a classe de problemas que podem ser resolvidos por um computador em um período de tempo razoável. Mais especificamente, os problemas P são aqueles para os quais o tempo necessário para encontrar uma solução pode ser descrito por uma função polinomial, como n^2. Em algoritmos de tempo polinomial, n é o tamanho do problema ou entrada, e o desenvolvimento desse problema ocorre a uma taxa razoável (neste caso, elevada à potência de dois).
Por outro lado, alguns problemas difíceis de NP podem ser resolvidos apenas por algoritmos com tempos de execução definidos por uma função exponencial, como 2^n, produzindo uma taxa de crescimento exponencial (como na disseminação da Covid-19). Já os problemas NP, como Aaronson descreve, é “a classe de esperanças frustradas e sonhos ociosos”. Ele é, no entanto, rápido em esclarecer um equívoco comum: nem todos os problemas de NP são difíceis. A classe NP de fato contém a classe P, porque problemas com soluções fáceis também são fáceis de verificar.
Os problemas mais desafiadores do NP geralmente têm aplicações práticas importantes. Para esses problemas, uma busca exaustiva de força bruta por uma solução provavelmente se arrastaria por um período de tempo impraticavelmente longo antes de produzir uma resposta. Se um algoritmo de busca de força bruta é o melhor algoritmo possível, então P não é igual a NP.
E entre os especialistas, esse aparentemente é o consenso, que alguns associam mais à crença religiosa: P ≠ NP. A maioria permite apenas uma pequena chance de que o oposto seja verdadeiro. “Eu daria uma chance de 2% a 3% de que P seja igual a NP”, diz Aaronson. “Essa é a aposta que eu faria”.
O resultado publicado em julho de 2021 ofereceu uma exata demonstração dessa possibilidade muito remota. Mas foi apenas o mais recente caso de uma longa tradição de provas que não são aprovadas. Em uma reviravolta digna do filme Monty Python, o artigo foi retirado do ar um dia após sua publicação, embora tenha reaparecido brevemente antes de desaparecer permanentemente. Era a versão mais recente de um artigo que o autor havia postado mais de 60 vezes no servidor de pré-impressão arXiv na última década. O editor-chefe da revista explicou no Twitter que o resultado foi rejeitado, mas em um caso de erro humano, a decisão de alguma forma mudou de “rejeitada” para “aceita” e o artigo chegou à publicação.
3. No início de agosto de 2021, quando encontrei Steve Cook em seu escritório no campus, ele não tinha visto nem ouvido falar da última confusão do problema “P versus NP”. Agora com 81 anos, ele se aposentou recentemente, já que sua memória estava falhando. “É por isso que temos James aqui”, disse ele — seu filho James, 36, também cientista da computação, participou da minha conversa com Steve durante minha visita. Steve estava no meio da limpeza de seu escritório. Uma lixeira gigantesca estava no meio da sala, cheia de velhas edições amareladas do Journal of Symbolic Logic.
Ao longo dos anos, Cook viu muitas provas que pretendiam resolver o problema “P versus NP”. Em 2000, após o Clay Mathematics Institute (EUA) classificá-lo como um dos sete “Problemas do Milênio” não resolvidos (a solução de cada um deles garante um prêmio de um milhão de dólares), Cook foi inundado por mensagens de pessoas que achavam que tinham conseguido. Todos os resultados estavam errados, se não claramente falsos. Cerca de metade afirmou ter provado que P é igual a NP; a outra metade foi na direção oposta. Não muito tempo atrás, uma pessoa afirmou ter provado ambos.
Cook, em seu artigo de 1971, conjecturou que P não é igual a NP (ele o expressou usando uma terminologia diferente comum na época). Desde então, ele passou uma quantidade significativa, embora indeterminada, de tempo trabalhando para provar seu ponto de vista. “Não tenho uma boa memória de trabalhar duro”, diz ele, mas seus colegas lembram que sempre que iam ao departamento no fim de semana, Steve estava lá em seu escritório.
A menos que ele esteja competindo em veleiros, Cook não tem pressa; ele gosta de dar tempo às ideias. E seus ex-alunos se lembram de uma clara falta de arrogância. A cientista da computação Anna Lubiw, da Universidade de Waterloo (Canadá), diz que quando ele ensinou o teorema de Cook, parte daquele artigo pioneiro, ele nunca se referiu a ele como o maioral e nunca deu a entender que ele era a pessoa por trás dos estudos. Maria Klawe, matemática e cientista da computação e presidente do Harvey Mudd College (EUA), diz que corrigia regularmente Cook quando ele se perdia ao ensinar as demonstrações que conhecia de trás pra frente: “Ele ficava preso e dizia: ‘Ok. Me diga como é o resto dessa demonstração.’” Cook também era famoso por ser modesto em pedidos de bolsas e relatórios sobre sua pesquisa, ele confessava: “Honestamente, fiz pouco progresso …”
No entanto, ele fez progressos ao incluir James para defender suas ideias. Logo no início, James demonstrou interesse em matemática e computação, aos nove anos, ele pediu a seu pai que lhe ensinasse álgebra booleana e lógica. Alguns anos atrás, depois de obter um doutorado em Berkeley (EUA) e passar um tempo no Google, ele partiu como pesquisador independente com foco em projetos diversos, alguns deles indiretamente ligados a “P versus NP”. E apesar do histórico, James, que tem uma notável semelhança com seu pai, não se intimida por ter herdado uma missão aparentemente interminável. Ele a considera como qualquer esforço matemático: é um quebra-cabeça divertido. “Tem que existir uma resposta para essas perguntas”, diz ele. “E é tipo, vamos lá, alguém tem que resolver isso. Vamos descobrir isso. Já faz muito tempo. É vergonhoso que ainda não saibamos a resposta”.
A falta de progresso não impediu esta comunidade de felizes Sísifos de comemorar o 50º aniversário da complexidade computacional. As festividades começaram em 2019, quando devotos de todo o mundo se reuniram no Fields Institute for Research in Mathematical Sciences, da Universidade de Toronto (Canadá), para um simpósio em homenagem a Cook. Christos Papadimitriou, um cientista da computação da Universidade de Columbia (EUA) que passou grande parte de sua carreira trabalhando no problema “P versus NP”, abriu o evento com uma palestra pública, relembrando não meio século, mas milênios.
Ele começou descrevendo antigas buscas por soluções, usando ferramentas algébricas ou régua e compasso, que ele considerava formas rudimentares de computação. A história de Papadimitriou finalmente chegou a Alan Turing, o matemático britânico cujo artigo de 1936 “On Computable Numbers” formalizou as noções de “algoritmo” e “computação”. Turing também demonstrou, com sua ideia de uma “máquina de computação universal”, que não existe uma maneira “mecânica” (isto é, realizada por uma máquina) para provar a verdade ou falsidade de afirmações matemáticas; nenhuma maneira sistemática de distinguir o provável do improvável.
Papadimitriou disse que considera o artigo de Turing a certidão de nascimento da ciência da computação, “e a certidão de nascimento diz que a ciência da computação nasceu com uma compreensão clara de suas próprias limitações”. Ele considerou a ciência da computação o único campo conhecido no mundo científico nascido com tal consciência, “em oposição a outras ciências, que como o resto de nós, entendem suas próprias limitações no final da meia-idade”.
Não demorou muito para que as ideias de Turing (e ideias semelhantes de outros) se concretizassem nos primeiros computadores, à medida que os cientistas se debatiam com questões sobre suas capacidades e limitações inerentes. No início da década de 1950, John von Neumann, o pioneiro húngaro-americano do computador moderno, “se gabava que seu algoritmo era polinomial, comparado ao titular exponencial”, lembrou Papadimitriou. Ele havia desafiado um algoritmo lento com um rápido. Este foi o início de uma nova teoria: a da complexidade computacional. A conclusão era que apenas algoritmos polinomiais eram bons, práticos ou capazes de resolver um problema, enquanto um algoritmo exponencial, de acordo com Papadimitriou, “era o equivalente algorítmico da morte”.
Cook começou a pensar sobre complexidade em meados da década de 1960. Enquanto trabalhava em seu doutorado em Harvard, ele ponderou se é possível provar, dados certos modelos computacionais, que a multiplicação é mais difícil do que a adição (continua sendo um problema em aberto).
Em 1967, de acordo com um livro sobre Cook, publicado pela Association for Computing Machinery (ACM), enquanto fazia pós-doutorado em Berkeley, ele escreveu observações que continham a semente de seu grande resultado. Ele elaborou uma formulação das classes de complexidade que vieram a ser conhecidas como P e NP, e levantou a questão de saber se P era igual a NP. (Na mesma época, outros, incluindo o cientista da computação Jack Edmonds, agora aposentado da Universidade de Waterloo, discutiam as mesmas ideias).
Mas o campo da ciência da computação estava apenas começando, e para a maioria dos cientistas e matemáticos essas ideias não eram familiares, senão mesmo estranhas. Depois de quatro anos no departamento de matemática de Berkeley, Cook foi considerado titular, mas não lhe foi oferecido um cargo. Ele tinha defensores no novo departamento de ciência da computação da universidade, e eles fizeram pressão para que ele conseguisse um cargo por lá, mas o reitor não queria oferecer uma posição a alguém que havia sido recusado por matemáticos ilustres.
A maioria dos teóricos da complexidade não sonham muito alto, optando por abordagens indiretas.
Em 1970, Cook mudou-se para a Universidade de Toronto. No ano seguinte, ele publicou sua grande descoberta. Submetido a um simpósio da ACM realizado naquele mês de maio em Shaker Heights, Ohio (EUA), o trabalho reforçou o conceito de complexidade e definiu uma forma de caracterizar os problemas mais difíceis em NP. Provou, em um resplendor de alquimia algorítmica, que um problema, conhecido como o problema da satisfatibilidade (procurar uma solução para uma fórmula dada um conjunto de restrições), era de certa forma o problema mais difícil em NP, e que todos os outros problemas NP poderiam ser reduzidos a isso.
Este foi um teorema crucial: se existe um algoritmo de tempo polinomial que resolve o problema de satisfatibilidade, então esse algoritmo servirá como uma chave-mestra, desbloqueando soluções para todos os problemas em NP. E se existe uma solução em tempo polinomial para todos os problemas em NP, então P = NP.
Entre os cientistas da computação, o teorema de Cook é icônico. O cientista da computação teórica da Universidade de Harvard, Leslie Valiant, relembra a conferência de 2019 e exatamente onde e quando ouviu falar do teorema pela primeira vez. Depois de terminar seus estudos universitários em matemática, ele começou um doutorado em ciência da computação. Embora houvesse cursos e graduações nesse campo incipiente, todos pareciam efêmeros, segundo ele, sem conteúdo intelectual profundo. “Era uma preocupação séria para as pessoas que faziam ciência da computação na época”, disse ele. Eles perguntaram: ‘Isso é um campo? Para onde está indo?” Um dia, Valiant encontrou o artigo de Cook. Ele o leu naquela mesma noite e se lembra: “Eu me transformei”, disse ele. “Em um instante, minhas preocupações com ciência da computação diminuíram. Para mim, esse artigo realmente deu origem ao campo. Acho que transformou a ciência da computação em algo substancial”.
E então, como conta a história, depois do teorema de Cook veio um dilúvio.
Em 1972, Dick Karp, um cientista da computação em Berkeley, depois de ler o artigo esotérico de Cook, demonstrou que muitos dos problemas computacionais clássicos com os quais ele estava intimamente familiarizado (essencialmente todos os problemas que ele não sabia como resolver, extraídos da programação matemática, pesquisa operacional, teoria dos grafos, combinatória e lógica computacional) possuíam a mesma propriedade transformacional que Cook havia encontrado com o problema da satisfatibilidade. No total, Karp encontrou 21 problemas, incluindo o problema da mochila (procurar a maneira ideal de empacotar um espaço restrito com os itens mais valiosos), o problema do caixeiro viajante (encontrar a rota mais curta possível para visitar cada cidade uma vez e retornar à cidade de origem) e o problema da árvore de Steiner (conectando de maneira ideal um conjunto de pontos com segmentos de linha de comprimento total mínimo).
Karp mostrou que essa coleção especial de problemas eram todos equivalentes, o que por sua vez demonstrou que o padrão identificado por Cook não era um fenômeno isolado, mas sim uma metodologia de classificação de poder e alcance surpreendentes. Foi uma espécie de teste decisivo, identificando a classe do que ficou conhecido como problemas “NP-completos”: uma solução para qualquer um resolveria todos eles.
Papadimitriou pensa nos “NP-completos” como uma ferramenta versátil. “Se você não pode resolver um problema, tente provar que é NP-completo, porque isso talvez economize muito tempo”, disse ele na palestra pública, você pode desistir de uma solução exata e passar a resolver uma aproximação ou variação do problema.
Ao longo da história, Papadimitriou vê o fenômeno dos NP-completos e a missão “P versus NP” como o destino da ciência da computação. Porque, em um acaso científico, um matemático soviético, Leonid Levin, convergiu para um resultado equivalente ao de Cook mais ou menos na mesma época. Levin, agora na Universidade de Boston (EUA), fez seu trabalho ainda na parte da Europa socialista, no período da Guerra Fria. Depois de receber mais atenção (ele imigrou para os Estados Unidos em 1978), o resultado ficou conhecido como o teorema de Cook-Levin.
Cerca de uma década depois, uma “carta perdida” foi descoberta nos arquivos do lógico austríaco Kurt Gödel na Universidade de Princeton (EUA). Em 1956, ele escreveu para von Neumann perguntando se um problema de lógica, que na linguagem moderna seria chamado de NP-completo, poderia ser resolvido em tempo polinomial. Ele opinou que “isso teria consequências de enorme magnitude”.
4. Enquanto meio século de trabalho não rendeu nada perto de uma solução, alguns resultados pelo menos chamam a atenção: um artigo em 2004 alegou ter uma prova para P = NP usando bolhas de sabão como um mecanismo de computação analógica (filme de sabão, alinhando-se naturalmente na configuração de energia mínima, de alguma forma resolve o problema da árvore de Steiner NP-completa).
Hoje em dia, é raro ver um cientista da computação que enfrente o problema de frente. Ron Fagin, por exemplo, um membro da IBM, na década de 1970, produziu o teorema de Fagin, que caracterizou a classe NP em termos de lógica matemática. E ele resolveu o problema mais de uma vez, mas os resultados nunca duraram mais do que alguns dias antes de ele encontrar um defeito. Fagin recentemente obteve financiamento para um projeto “P versus NP” do programa Exploratory Challenges da IBM, que apoia pesquisas ousadas. Ao explicar por que ele insiste nisso, ele gosta de citar Theodore Roosevelt, que disse que é muito melhor “ousar coisas poderosas” do que estar entre aqueles que “vivem nessa penumbra cinzenta que não conhece vitória nem derrota”.
Mas a maioria dos teóricos da complexidade não sonham muito alto, optando por abordagens indiretas, vendo o problema em outro ângulo, mudando sua forma ou estrutura, explorando ambientes relacionados e reduzindo ainda mais o arsenal de ferramentas que poderiam ser empregadas contra ele (muitas agora são conhecidas por serem inúteis).
O cientista da computação do MIT, Ryan Williams, tenta atacar o problema de cima e de baixo, investigando a natureza dos “limites superiores” e “limites inferiores” nos principais problemas computacionais. Um limite superior, em termos simples, é uma afirmação matemática específica de que existe um algoritmo concreto que resolve um determinado problema sem exceder uma certa quantidade de recursos (tempo, memória, energia). Um limite inferior é o oposto intangível: é uma afirmação geral de impossibilidade, mostrando que tal algoritmo não existe universalmente. Um foco da pesquisa de Williams é tornar os limites inferiores construtivos e concretos, objetos matemáticos com características descritíveis. Ele acredita que abordagens mais construtivas para limites inferiores são “precisamente o que está faltando nas abordagens atuais na teoria da complexidade computacional”.
Williams determinou que a probabilidade de que P ≠ NP seja de uns moderados 80%. Mas ultimamente alguns pesquisadores da área estão expressando dúvidas até mesmo sobre esse nível de certeza. “Cada vez mais, estou começando a me perguntar se P é igual a NP”, diz Toniann Pitassi, cientista da computação da Universidade de Toronto e ex-aluna de doutorado de Cook. Sua abordagem para contornar o problema é estudar tanto os análogos expandidos quanto os reduzidos, modelos mais difíceis e mais fáceis. “Às vezes, generalizar a pergunta a torna mais clara”, diz ela. Mas, no geral, ela não alcançou clareza: “A maioria das pessoas pensam que P não é igual a NP. E eu não sei. Talvez seja só eu, mas sinto que está ficando cada vez menos claro que essa é a verdade”.
Pitassi ressalta que, historicamente, resultados surpreendentes às vezes surgiram do nada, e que algumas aparentes impossibilidades foram mostradas como possíveis por designers de algoritmos. O mesmo pode acontecer com “P versus NP”, talvez daqui a 50 anos ou um século. Um dos resultados mais importantes em toda a teoria da complexidade, por exemplo, foi alcançado por David Barrington, da Universidade de Massachusetts, em Amherst (EUA), em 1989. A essência disso (para nossos propósitos) é que ele desenvolveu um algoritmo inteligente, que começou a fazer algo que aparentemente deveria exigir uma quantidade ilimitada de memória, mas na verdade usou uma quantidade surpreendentemente pequena, apenas cinco bits de informação, o suficiente para especificar um número entre um e 32 (inclusive) ou uma palavra de duas letras.
Um resultado mais recente e relacionado, de 2014, pegou James Cook de surpresa. Com base no teorema de Barrington, ele usa a memória de uma maneira maravilhosamente estranha. Conforme sugerido no título do artigo, escrito pelo professor da Universidade de Amsterdã (Holanda) Harry Buhrman e seus colaboradores, trata-se de “computar com memória completa”. James pode recitar o parágrafo introdutório do artigo praticamente palavra por palavra:
Imagine o seguinte cenário. Você deseja realizar um cálculo que exija mais memória do que você tem atualmente disponível em seu computador. Uma maneira de lidar com esse problema é instalar um novo disco rígido. Acontece que você tem um disco rígido, mas está cheio de dados, fotos, filmes, arquivos, etc. Você não precisa acessar esses dados no momento, mas também não deseja apagá-los. Você poderia usar esse disco rígido para seu cálculo, possivelmente alterando temporariamente seu conteúdo, garantindo que, quando o cálculo estiver concluído, o disco rígido retorne ao seu estado original com todos os dados intactos?
A resposta, contraintuitivamente, é sim.
James pensa nisso como uma “memória emprestada”. Depois que o choque desse resultado passou, ele se divertiu descobrindo como aplicá-lo a um problema específico, continuar de onde seu pai havia parado.
Algumas décadas atrás, Steve Cook seguiu em frente focando em outros problemas relacionados à teoria da complexidade. Em um deles, ele fez uma conjectura sobre a quantidade de memória que um algoritmo precisaria para resolver o problema, chegando a um mínimo absoluto. Em 2019, James, junto com Ian Mertz, um dos alunos de doutorado de Pitassi, testou a ideia poética de emprestar memória e provou que era necessária ainda menos memória. O resultado não chegou a refutar a conjectura de seu pai, mas marca um pequeno passo à frente na busca por uma grande complexidade computacional.
E os problemas na teoria da complexidade, observa James, às vezes têm um efeito dominó, se houver uma demonstração de dados em uma parte crítica, todas as peças caem. Os resultados inovadores, os mais importantes, vêm de uma longa linha de trabalho, desencadeados por muitas pessoas diferentes, fazendo progressos incrementais e estabelecendo conexões entre diferentes questões, até que finalmente surge um grande resultado.
Ele também lança um aviso: enquanto o algoritmo P = NP acabaria sendo muito rápido, há também um cenário em que P = NP poderia ser uma decepção. Pode acontecer que um algoritmo P capaz de resolver o problema NP-completo esteja em uma escala de tempo de, digamos, n^100. “Tecnicamente, isso se enquadra em P: é um polinômio”, diz James. “Mas n^100 ainda é muito impraticável”, isso significaria que quaisquer problemas consideráveis ainda estariam fora de alcance em escalas de tempo humanas.
Isso, é claro, assumindo que podemos encontrar o algoritmo em primeiro lugar. O especialista em algoritmos da Universidade de Stanford (EUA), Donald Knuth, mudou de ideia nos últimos anos: “ele deu a volta por cima”. Sua intuição é que P realmente é igual a NP, mas que provavelmente nunca seremos capazes de fazer uso desse fato, porque na verdade não conheceremos nenhum dos algoritmos que funcionariam. Há um número impressionante de algoritmos, explica Knuth, mas a maioria deles está além do nosso alcance. Assim, enquanto alguns pesquisadores podem insistir que nenhum algoritmo P = NP existe, Knuth afirma que “é mais provável que nenhum algoritmo de tempo polinomial seja definido, isto é, escrito como um programa real, por meros mortais”.
Para Papadimitriou, qualquer resposta acalmaria essa obsessão perpétua. Ele acredita que o problema “P versus NP” pertence ao reino dos enigmas científicos fundamentais, como a origem da vida e a unificação dos campos de força da natureza. É o tipo de quebra-cabeça profundo e consequente, “concreto, mas universal”, disse ele, “que acrescenta significado não apenas à ciência, mas à própria vida humana”.
“Imagine que temos sorte e somos capazes de espremer mais alguns milhares de anos deste planeta, contra as probabilidades e apesar das excentricidades”, disse ele. “E nós não resolvemos esses problemas. Qual é o ponto?!”
MIT Technology Review
