A Jornada de 50 Anos da Teoria da Complexidade até os Limites do Conhecimento | Revista Quanta

Na primeira semana do semestre de outono de 2007, Marco Carmosino se arrastou para uma aula de matemática exigida para todos os cursos de ciência da computação na Universidade de Massachusetts, Amherst. Carmosino, um estudante do segundo ano, estava pensando em largar a faculdade para criar videogames. Então o professor fez uma pergunta simples que mudaria o curso de sua vida: como você sabe que a matemática realmente funciona?

“Isso me fez sentar e prestar atenção”, lembrou carmosino, agora um cientista da computação teórico na IBM. Ele se inscreveu para um seminário opcional sobre o trabalho de Kurt Gödel, cujos estonteantes argumentos auto-referenciais expuseram pela primeira vez os limites do raciocínio matemático e criaram a base para todos os trabalhos futuros sobre os limites fundamentais da computação. Era muito para absorver.

“Não entendi 100%”, disse Carmosino. “Mas eu sabia que queria.”

Hoje, até mesmo pesquisadores experientes encontram pouca compreensão quando confrontam a questão central em aberto na ciência da computação teórica, conhecida como o problema P versus NP. Em essência, essa questão pergunta se muitos problemas computacionais há muito considerados extremamente difíceis podem realmente ser resolvidos facilmente (por meio de um atalho secreto que ainda não descobrimos) ou se, como a maioria dos pesquisadores suspeita, eles realmente são difíceis. O que está em jogo é nada menos do que a natureza do que é cognoscível.

Apesar de décadas de esforço de pesquisadores no campo da teoria da complexidade computacional - o estudo de tais questões sobre a dificuldade intrínseca de diferentes problemas - uma resolução para a questão P versus NP permaneceu indefinida. E nem mesmo está claro por onde uma suposta prova deveria começar.

“Não há roteiro”, disse Michael Sipser, um veterano teórico da complexidade do Instituto de Tecnologia de Massachusetts que passou anos lutando com o problema na década de 1980. “É como se você estivesse indo para o deserto.”

Parece que provar que problemas computacionais são difíceis de resolver é em si uma tarefa difícil. Mas por que é tão difícil? E quão difícil é? Carmosino e outros pesquisadores no subcampo da metacomplexidade reformulam questões como essa como problemas computacionais, impulsionando o campo para frente ao voltar as lentes da teoria da complexidade para si mesma.

“Você pode pensar: 'OK, isso é legal. Talvez os teóricos da complexidade tenham enlouquecido'”, disse Rahul Ilango, um estudante de pós-graduação do MIT que produziu alguns dos resultados recentes mais empolgantes no campo.

Ao estudar estas questões introspectivas, os investigadores aprenderam que a dificuldade de provar a dureza computacional está intimamente ligada a questões fundamentais que podem, à primeira vista, parecer não relacionadas. Quão difícil é detectar padrões ocultos em dados aparentemente aleatórios? E se existem problemas verdadeiramente difíceis, com que frequência são difíceis?

“Ficou claro que a meta-complexidade está perto do cerne das coisas”, disse Scott Aaronson, um teórico da complexidade da Universidade do Texas, Austin.

Esta é a história da longa e sinuosa trilha que levou os pesquisadores do problema P versus NP à metacomplexidade. Não foi uma jornada fácil - o caminho está repleto de curvas falsas e bloqueios de estradas, e volta a si mesmo repetidamente. No entanto, para os pesquisadores de metacomplexidade, essa jornada em uma paisagem desconhecida é sua própria recompensa. Comece a fazer perguntas aparentemente simples, disse Valentim Kabanets, um teórico da complexidade da Universidade Simon Fraser, no Canadá, e “você não tem ideia para onde está indo”.

Desconhecidos Conhecidos

O problema P versus NP deve seu nome sem brilho ao hábito dos teóricos da complexidade de classificar problemas computacionais em “classes de complexidade” com rótulos sugestivos de símbolos Nasdaq. Um problema computacional é aquele que pode, em princípio, ser resolvido por um algoritmo — uma lista de instruções especificada com precisão. Mas nem todos os algoritmos são igualmente úteis, e a variação entre os algoritmos sugere diferenças fundamentais entre problemas em diferentes classes. O desafio para os teóricos da complexidade é transformar essas dicas em teoremas rigorosos sobre as relações entre as classes de complexidade.

Essas relações refletem verdades imutáveis ​​sobre computação que vão muito além de qualquer tecnologia específica. “É como descobrir as leis do universo”, disse Kabanets.

“P” e “NP” são os dois membros mais famosos de uma crescente zoológico de centenas de classes de complexidade. Grosso modo, P é a classe de problemas que podem ser resolvidos facilmente, como colocar uma lista em ordem alfabética. NP é a classe de problemas com soluções facilmente verificáveis, como quebra-cabeças sudoku. Como todos os problemas facilmente solucionáveis ​​também são fáceis de verificar, os problemas em P também estão em NP. Mas alguns problemas de NP parecem difíceis de resolver - você não pode intuir imediatamente a solução para um quebra-cabeça de sudoku sem primeiro experimentar muitas possibilidades. Será que essa aparente dureza é apenas uma ilusão - que existe um único truque simples para resolver todos os problemas facilmente verificáveis?

Se sim, então P = NP: As duas classes são equivalentes. Se for esse o caso, deve haver algum algoritmo que torne trivial a resolução de enormes quebra-cabeças de sudoku, a otimização de rotas marítimas globais, a quebra da criptografia de última geração e a automatização das provas de teoremas matemáticos. Se P ≠ NP, então muitos problemas computacionais que são solucionáveis ​​em princípio permanecerão, na prática, para sempre fora do nosso alcance.

Os pesquisadores se preocuparam com os limites do raciocínio matemático formal muito antes de o problema P versus NP ser articulado pela primeira vez – na verdade, muito antes do início da ciência da computação moderna. Em 1921, lutando com a mesma questão que atrairia a atenção de Carmosino quase um século depois, o matemático David Hilbert propôs um programa de pesquisa para fundamentar a matemática na certeza absoluta. Ele esperava partir de algumas suposições simples, chamadas axiomas, e derivar uma teoria matemática unificada que atendesse a três critérios principais.

A primeira condição de Hilbert, a consistência, era o requisito essencial para que a matemática fosse livre de contradições: se duas afirmações contraditórias pudessem ser provadas a partir dos mesmos axiomas, toda a teoria seria irrecuperável. Mas uma teoria pode estar livre de contradições e ainda ser limitada em seu alcance. Essa foi a motivação para a segunda condição de Hilbert, a completude: a exigência de que todas as afirmações matemáticas sejam comprovadamente verdadeiras ou comprovadamente falsas. Seu terceiro critério, decidibilidade, exigia um procedimento mecânico inequívoco para determinar se qualquer afirmação matemática era verdadeira ou falsa. Dirigindo-se a uma conferência em 1930, Hilbert declarou: “Nosso slogan será 'Devemos saber, saberemos'”.

Apenas um ano depois, Gödel deu o primeiro golpe no sonho de Hilbert. Ele provou que uma afirmação autodestrutiva como “esta afirmação é improvável” poderia ser derivada de qualquer conjunto apropriado de axiomas. Se tal afirmação for realmente improvável, a teoria está incompleta, mas se for demonstrável, a teoria é inconsistente – um resultado ainda pior. No mesmo artigo, Gödel também provou que nenhuma teoria matemática jamais poderia provar sua própria consistência.

Os pesquisadores ainda tinham esperança de que uma futura teoria da matemática, embora necessariamente incompleta, pudesse ser decidida. Talvez eles pudessem desenvolver procedimentos que identificassem todas as declarações prováveis ​​enquanto evitavam proposições irritantes como a de Gödel. O problema era que ninguém sabia raciocinar sobre esses procedimentos hipotéticos.

Então, em 1936, um estudante de pós-graduação de 23 anos chamado Alan Turing reformulou a condição de decidibilidade de Hilbert na então desconhecida linguagem da computação e desferiu um golpe fatal. Turing formulou um modelo matemático - agora conhecido como Máquina de Turing — que poderia representar todos os algoritmos possíveis e mostrou que se o procedimento de Hilbert existisse, ele se enquadraria neste modelo. Ele então usou métodos autorreferenciais como o de Gödel para provar a existência de declarações indecidíveis – ou, equivalentemente, problemas incomputáveis ​​que nenhum algoritmo poderia resolver.

O programa de Hilbert estava em ruínas: haveria para sempre limites fundamentais sobre o que poderia ser provado e o que poderia ser calculado. Mas à medida que os computadores evoluíram de abstrações teóricas para máquinas reais, os investigadores perceberam que a simples distinção de Turing entre problemas solucionáveis ​​e insolúveis deixava muitas questões sem resposta.

Na década de 1960, os cientistas da computação desenvolveram algoritmos rápidos para resolver alguns problemas, enquanto para outros os únicos algoritmos conhecidos eram terrivelmente lentos. E se a questão não fosse apenas se os problemas são solucionáveis, mas quão difíceis eles são de resolver?

“Surge uma teoria rica e não sabemos mais as respostas”, disse Carmosino.

Caminhos Divergentes

Para ilustrar como as questões sobre dureza podem ser desconcertantes, vamos considerar um par de problemas intimamente relacionados envolvendo gráficos. São redes de pontos, chamados nós, conectados por linhas, chamadas arestas. Os cientistas da computação os usam para modelar tudo, desde computação quântica ao fluxo de tráfego.

Suponha que você receba um gráfico e peça para encontrar algo chamado caminho hamiltoniano — uma rota que passa por cada nó exatamente uma vez. Este problema é claramente solucionável em princípio: há apenas um número finito de caminhos possíveis, portanto, se tudo mais falhar, você pode apenas verificar cada um. Tudo bem se houver apenas alguns nós, mas mesmo para gráficos um pouco maiores, o número de possibilidades sai de controle, rapidamente tornando inútil esse algoritmo simples.

Existem algoritmos de caminho hamiltoniano mais sofisticados que lutam melhor, mas o tempo que os algoritmos requerem para resolver o problema invariavelmente cresce exponencialmente com o tamanho do gráfico. Os gráficos não precisam ser muito grandes antes mesmo dos melhores algoritmos que os pesquisadores descobriram não conseguirem encontrar um caminho “em um período de tempo razoável”, disse Russel Impagliazzo, um teórico da complexidade da Universidade da Califórnia, San Diego. “E por 'quantidade de tempo razoável', quero dizer 'antes do universo acabar'.”

O problema do caminho hamiltoniano tem outra propriedade interessante. Se alguém afirma ter encontrado um caminho hamiltoniano em um determinado gráfico, você pode verificar rapidamente se a solução é válida, mesmo que o gráfico seja muito grande. Tudo o que você precisa fazer é seguir o caminho e marcar os nós um por um, verificando se não marcou nenhum nó duas vezes. Se nenhum nó estiver faltando no final, o caminho é hamiltoniano.

O tempo necessário para executar esse algoritmo de verificação de solução é proporcional ao tamanho do gráfico. Isso o coloca na categoria mais ampla de algoritmos polinomiais, cujos tempos de execução aumentam como funções polinomiais do tamanho do gráfico. O crescimento polinomial é manso em comparação com o crescimento exponencial, portanto, os algoritmos polinomiais permanecem viáveis ​​mesmo em gráficos grandes. “É dramaticamente mais eficiente”, disse Carmosino.

O problema do caminho hamiltoniano tem uma assimetria gritante: você pode verificar uma solução correta usando um algoritmo polinomial rápido, mas para encontrar uma solução você precisará de um algoritmo exponencial lento. Essa assimetria pode não parecer surpreendente — é mais fácil reconhecer uma obra-prima artística do que criá-la, mais fácil verificar uma prova matemática do que provar um novo teorema — mas nem todos os problemas computacionais têm este carácter assimétrico. Na verdade, um problema muito semelhante ao de encontrar caminhos hamiltonianos se comporta de maneira bem diferente.

Suponha que você receba novamente um gráfico, mas agora seja solicitado a encontrar um “caminho euleriano” que cruze todas as arestas exatamente uma vez. Novamente, há um algoritmo polinomial para verificar possíveis soluções, mas desta vez também há um algoritmo polinomial para resolver o problema. Nenhuma assimetria aqui. Na teoria da complexidade, alguns caminhos parecem mais fáceis de encontrar do que outros.

Tanto o problema do caminho hamiltoniano quanto o problema do caminho euleriano estão na classe de complexidade NP, definida para incluir todos os problemas cujas soluções podem ser verificadas por algoritmos polinomiais. O problema do caminho euleriano também se enquadra na classe P porque um algoritmo polinomial pode resolvê-lo, mas, ao que tudo indica, isso não é verdade para o problema do caminho hamiltoniano. Por que esses dois problemas de gráficos, tão superficialmente semelhantes, diferem tão dramaticamente? Essa é a essência do problema P versus NP.

Universalmente difícil

A princípio, as classes de complexidade pareciam categorias convenientes para classificar problemas semelhantes, mas não diretamente relacionados - ninguém suspeitava que encontrar caminhos hamiltonianos tivesse algo a ver com outros problemas computacionais difíceis.

Então, em 1971, um ano depois de se mudar para a Universidade de Toronto após ter sido negado o cargo nos Estados Unidos, o teórico da complexidade Stephen Cook publicou um resultado extraordinário. Ele identificou um problema NP particular com uma característica estranha: se existe um algoritmo polinomial que pode resolver esse problema, ele também pode resolver todos os outros problemas em NP. O problema “universal” de Cook, ao que parecia, era uma coluna solitária sustentando a classe de problemas aparentemente difíceis, separando-os dos problemas fáceis abaixo. Resolva esse problema e o resto do NP desabará.

Cook suspeitava que não havia algoritmo rápido para seu problema universal, e ele disse isso no meio do artigo, acrescentando: “Acho que vale a pena gastar um esforço considerável tentando provar essa conjectura”. “Esforço considerável” seria um eufemismo.

Na mesma época, um estudante de pós-graduação na União Soviética chamado Leonid Levin provou um resultado semelhante, exceto que ele identificou vários problemas universais diferentes. Além disso, o teórico americano da complexidade Ricardo Karp provou que a propriedade de universalidade identificada por Cook (e por Levin, embora Karp e Cook só conhecessem o trabalho de Levin anos depois) era praticamente universal. Quase todos os problemas NP sem um algoritmo polinomial conhecido - isto é, quase todos os problemas facilmente verificáveis ​​que pareciam difíceis - tinham a mesma propriedade, que ficou conhecida como NP-completude.

Isso significa que todos os problemas NP-completos — o problema do caminho hamiltoniano, sudoku e milhares de outros – são equivalentes num sentido preciso. “Você tem todas essas diferentes tarefas naturais, e todas elas magicamente acabam sendo a mesma tarefa”, disse Ilango. “E ainda não sabemos se essa mesma tarefa é possível ou não.”

Resolver a dificuldade de qualquer problema NP-completo seria suficiente para resolver a questão P versus NP. Se P ≠ NP, a distinção entre problemas fáceis e difíceis é sustentada por milhares de colunas que são todas igualmente fortes. Se P = NP, todo o edifício está à beira do colapso, apenas esperando que uma única peça caia.

Cook, Levin e Karp unificaram o que pareciam muitos problemas não relacionados. Agora, tudo o que os teóricos da complexidade tinham que fazer era resolver um problema: P = NP ou não?

Cinquenta anos depois, a pergunta continua sem resposta. Kabanets comparou o raciocínio sobre os limites da computação ao levantamento de um vasto território sem qualquer noção do quadro geral. Um ser de poder computacional ilimitado poderia espiar do topo de uma montanha e abranger toda a paisagem de uma só vez, mas meros mortais não podem contar com esse tipo de vantagem. “Aqueles de nós no sopé da montanha podem tentar pular para cima e para baixo para ter uma visão melhor”, disse ele.

Suponha que P = NP. Para provar isso, os pesquisadores precisariam encontrar um algoritmo rápido para um problema NP-completo, que pode estar escondido em algum canto obscuro dessa vasta paisagem. Não há garantia de que o encontrarão tão cedo: os teóricos da complexidade ocasionalmente descoberto algoritmos engenhosos para problemas aparentemente difíceis (embora não NP-completos) somente após décadas de trabalho.

Agora suponha que P ≠ NP. Provar isso parece ainda mais difícil. Os teóricos da complexidade teriam que estabelecer que nenhum algoritmo rápido poderia existir, efetivamente antecipando e frustrando os melhores esforços de todos os futuros pesquisadores.

Não saber por onde começar faz parte do problema. Mas não é como se os pesquisadores não tivessem tentado. Ao longo das décadas, eles atacaram o problema de vários ângulos e encontraram o caminho bloqueado a cada curva. “É uma das verdades mais flagrantes da ciência da computação teórica”, disse Carmosino. “Quando você tem um fenômeno tão durável, você quer alguma explicação.”

No último ano de faculdade de Carmosino, sua curiosidade o levou de Gödel a um curso de pós-graduação em teoria da complexidade. Ele ficou surpreso ao perceber que estava gastando mais tempo com o dever de casa do que com seu projeto de paixão, um programa de computador que aprenderia a estrutura narrativa dos contos de fadas e geraria novos.

“Pensei: 'Nossa, preciso levar isso a sério'”, lembrou Carmosino. Em pouco tempo, ele estava tão absorto no assunto que seu mentor gentilmente sugeriu que reconsiderasse seus planos de pós-graduação.

“Ele disse: 'Sabe, se você quiser continuar fazendo isso, se quiser continuar fazendo ciência da computação teórica e teoria da complexidade, você pode: isso se chama pós-graduação'”, disse Carmosino. Após concluir o mestrado, mudou-se para San Diego em 2012 para fazer doutorado orientado por Impagliazzo.

O principal objetivo de Carmosino, num primeiro momento, foi compreender melhor uma papel de referência de duas décadas antes que havia capturado sua imaginação. Esse papel, pelos teóricos da complexidade Alexandre Razborov e Steven Rudich, mostrou que uma certa estratégia “natural” para provar P ≠ NP quase certamente falharia, porque o sucesso viria a um custo alto – a quebra completa da criptografia – que os pesquisadores consideravam muito improvável. Os pesquisadores interpretaram o resultado de Razborov e Rudich como uma barreira para essa abordagem popular de provar P ≠ NP.

Essa “barreira de provas naturais” é apenas uma das muitas barreiras conhecidas para resolver problemas em aberto na teoria da complexidade. Cada um age como um obstáculo, avisando que um caminho aparentemente promissor é, na verdade, um beco sem saída. Juntas, essas barreiras indicam que qualquer prova que resolva o problema P versus NP teria que ser radicalmente diferente de qualquer coisa usada no passado; é por isso que a maioria dos pesquisadores acredita que uma solução ainda está longe. Mas pelo menos as barreiras dizem a eles onde não procurar.

“A teoria da complexidade é amaldiçoada e abençoada com tantas barreiras”, disse Ilango.

Quando Carmosino encontrou a barreira das provas naturais, já tinha quase 20 anos. Mas ele suspeitava que trazia mais lições para os pesquisadores. Esse sentimento seria um dia justificado quando ele e três colegas provaram um resultado surpreendente ao examinar a barreira das provas naturais sob a perspectiva da metacomplexidade. A prova deles foi um dos poucos resultados importantes que despertou um novo interesse na metacomplexidade, levando a uma onda de progresso nos últimos anos.

Mas para seguir o caminho que vai da barreira das provas naturais até à metacomplexidade, teremos de regressar ao ponto onde deixámos os investigadores na década de 1970, quando começaram a abordar o problema P versus NP. O que tornou tão difícil provar os problemas?

Um caminho tortuoso

A princípio, os pesquisadores tentaram provar P ≠ NP — isto é, provar que alguns problemas NP não são solucionáveis ​​por nenhum algoritmo polinomial possível — usando variações das técnicas que Turing havia usado para provar que alguns problemas não são solucionáveis ​​por qualquer algoritmo. . Mas eles rapidamente descoberto uma prova de que esses métodos não funcionariam - a primeira grande barreira para resolver a questão P versus NP. Então eles começaram a procurar outra abordagem, e logo encontraram uma no trabalho do contemporâneo de Turing. Claude Shannon.

Shannon, que cresceu em uma pequena cidade no norte de Michigan, parecia uma figura improvável para inaugurar a era da informação. No entanto, ele exemplificou a natureza interdisciplinar da disciplina emergente da ciência da computação, sentindo-se igualmente em casa na engenharia elétrica e na lógica matemática. No dele tese de mestrado, Shannon mostrou como os circuitos feitos de interruptores eletromecânicos podem representar expressões lógicas envolvendo variáveis ​​booleanas — quantidades que podem assumir apenas dois valores (como verdadeiro ou falso, ou 1 e 0).

Nessas expressões, as variáveis ​​booleanas são ligadas pelas “portas lógicas” AND, OR e NOT. A expressão elementar A e B, por exemplo, é verdadeira quando ambos A e B são verdadeiros, e falso caso contrário; A OU B, por outro lado, é verdadeiro se pelo menos uma das duas variáveis ​​for verdadeira. Uma porta NOT é ainda mais simples: ela inverte o valor de uma única variável. Com o suficiente desses blocos de construção básicos, você pode realizar qualquer cálculo.

“Quando você olha para o seu computador, no final do dia, o que ele está fazendo? Está rodando um circuito”, disse Ilango.

O trabalho de Shannon sugeriu uma nova maneira de os teóricos pensarem sobre a dificuldade dos problemas computacionais, chamada de “complexidade do circuito”, embora os circuitos em questão sejam apenas abstrações matemáticas. Por um tempo, os pesquisadores pensaram que essa abordagem poderia ser o caminho para resolver P versus NP, mas eventualmente a trilha esbarrou na barreira das provas naturais.

A estrutura da complexidade do circuito requer repensar os conceitos mais básicos do modelo de computação de Turing. Aqui, em vez de problemas computacionais e os algoritmos que os resolvem, os pesquisadores consideram funções booleanas e os circuitos que os calculam. Uma função booleana recebe variáveis ​​booleanas — verdadeiros e falsos, 1s e 0s — e gera verdadeiro ou falso, 1 ou 0. E, como um algoritmo, um circuito descreve um procedimento para produzir uma saída dada qualquer entrada.

“Meu entendimento é que as pessoas começaram a trabalhar na complexidade do circuito porque decidiram que as máquinas de Turing eram muito complicadas”, disse Ryan Williams, um teórico da complexidade do MIT. “Podemos estudar os circuitos portão por portão.”

Assim como pode haver muitos algoritmos para resolver qualquer problema computacional, alguns mais rápidos do que outros, muitos circuitos diferentes podem calcular qualquer função booleana, alguns com menos portas do que outros. Os pesquisadores definem a complexidade do circuito de uma função como o número total de portas no menor circuito que a calcula. Para uma função com um número fixo de variáveis ​​de entrada, a complexidade do circuito também é um número fixo — maior para algumas funções do que para outras.

Mas, em muitos casos, você pode considerar versões mais complicadas da mesma função aumentando o número de variáveis ​​de entrada, assim como pode tornar o problema do caminho hamiltoniano mais difícil considerando gráficos maiores. Os pesquisadores então consideram a mesma pergunta que fazem ao estudar os tempos de execução do algoritmo: o número mínimo de portas necessárias para calcular uma função booleana cresce polinomialmente ou exponencialmente conforme o número de variáveis ​​de entrada aumenta? Os pesquisadores chamam essas duas categorias de funções de “fáceis de calcular” e “difíceis de calcular”, respectivamente.

Uma função booleana fácil de calcular é semelhante a um problema computacional da classe P — que pode ser resolvido por um algoritmo executado em tempo polinomial. Mas também existem funções análogas a problemas NP difíceis, onde a melhor maneira que os pesquisadores descobriram para calcular versões progressivamente maiores requer um número exponencialmente crescente de portas, mas a resposta pode ser facilmente verificada. Se os teóricos da complexidade pudessem provar que realmente não há melhor maneira de calcular tal função, isso implicaria P ≠ NP.

Esta foi a estratégia que a maioria dos teóricos da complexidade perseguiu na década de 1980. E as probabilidades estavam do lado deles. Shannon tinha provou em 1949 que quase toda tabela de verdade booleana (que é apenas uma longa lista de todas as entradas e saídas possíveis de uma função booleana de tamanho fixo) tem complexidade de circuito praticamente a mais alta possível. Ele usou um argumento incrivelmente simples: há muito menos maneiras de combinar um pequeno número de portas do que maneiras de combinar muitas portas.

“Simplesmente não há circuitos pequenos suficientes para todos”, disse Aaronson.

Assim, os teóricos da complexidade se viram em uma situação curiosa. Se quase toda tabela de verdade tem alta complexidade de circuito, quase toda função booleana deve ser difícil de calcular. Os pesquisadores apenas tiveram que identificar uma única função que também era conhecida por estar na classe NP. Quão difícil isso poderia ser?

Cripto Irmãos

No início, o progresso foi rápido. Em 1981, Sipser e dois colaboradores provou que uma certa função booleana era definitivamente difícil de calcular se eles usassem circuitos com certas restrições sobre como os portões poderiam ser organizados.

“A fantasia era que você seria capaz de provar coisas sobre esses modelos restritos e, em seguida, desenvolver o que aprendeu para trabalhar com cada vez menos restrições”, disse Sipser.

Em 1985, Razborov deu o próximo grande passo. Ele tinha acabado de começar a pós-graduação em Moscou e juntou-se acidentalmente ao esforço enquanto abordava um problema em um ramo diferente da matemática, onde descobriu-se que resolver o problema P versus NP era um pré-requisito.

“Tive sorte de não saber o quão difícil era esse problema”, disse Razborov. “Caso contrário, talvez eu nem tivesse começado.”

Razborov analisou circuitos contendo apenas portas AND e OR, e provou que uma função específica era difícil de calcular usando tais circuitos, não importa como as portas fossem arranjadas - além do mais, essa função era conhecida por ser NP-completa. Tudo o que os pesquisadores tiveram que fazer para resolver P versus NP foi estender as técnicas de Razborov para circuitos com portas NOT.

“Havia uma espécie de sentimento universal de que mais um passo, mais um ataque, e conseguiríamos”, disse Razborov. Mas não foi isso que aconteceu. O próprio Razborov provou que seu método falharia se as portas NOT fossem adicionadas à mistura, e ninguém poderia encontrar outro caminho a seguir. Com o passar dos anos, ele começou a se perguntar por que a trilha havia se esgotado.

Nos Estados Unidos, Rudich ponderava a mesma questão. Ele e Impagliazzo eram colegas de faculdade que fizeram pós-graduação juntos. A amizade deles foi despertada por um fascínio compartilhado pelas provas autorreferenciais de Gödel e Turing e suas implicações para os fundamentos da matemática e da ciência da computação.

“Nossa piada era que receberíamos um botão que dizia 'auto-referência'”, disse Impagliazzo.

Como estudantes de pós-graduação, Rudich e Impagliazzo trabalharam nos fundamentos teóricos da complexidade da criptografia, um assunto que oferece talvez a melhor motivação prática para tentar provar P ≠ NP. Os criptógrafos ocultam mensagens secretas camuflando-as em “pseudo-aleatoriedade” – uma mensagem criptografada dessa maneira parecerá uma confusão aleatória de números para qualquer bisbilhoteiro, mas ainda pode ser decodificada pelo destinatário pretendido. Mas como você pode ter certeza de que um aspirante a bisbilhoteiro achará muito difícil decifrar o código?

É aí que entra a teoria da complexidade. Os métodos de criptografia mais usados ​​atualmente são todos baseados em problemas NP aparentemente difíceis — para descriptografar a mensagem, um invasor precisaria de um algoritmo rápido ainda não descoberto para resolver o problema. Para estabelecer que esses métodos são realmente seguros, uma coisa que você precisa fazer é provar que P ≠ NP. Sem uma prova, disse Sipser, tudo o que você pode fazer é “esperar que a pessoa de quem você está tentando esconder o segredo não seja um matemático melhor do que você”.

Embora fascinante por si só, a criptografia parecia muito distante dos argumentos autorreferenciais que primeiro atraíram Rudich e Impagliazzo para o campo. Mas enquanto Rudich lutava para entender por que a abordagem da complexidade do circuito havia estagnado, ele começou a perceber que os dois assuntos não estavam tão distantes, afinal. A estratégia que os investigadores adoptaram nas suas tentativas de provar que P ≠ NP tinha um carácter autodestrutivo que lembrava a famosa proposição de Gödel “esta afirmação é improvável” – e a criptografia poderia ajudar a explicar porquê. Na Rússia, Razborov descobriu uma conexão semelhante na mesma época. Estas foram as sementes da barreira das provas naturais.

A tensão no cerne da barreira das provas naturais é que a tarefa de distinguir funções de alta complexidade das de baixa complexidade é semelhante à tarefa de distinguir a verdadeira aleatoriedade da pseudo-aleatoriedade usada para criptografar mensagens. Gostaríamos de mostrar que funções de alta complexidade são categoricamente diferentes de funções de baixa complexidade, para provar que P ≠ NP. Mas também gostaríamos que a pseudo-aleatoriedade fosse indistinguível da aleatoriedade, para termos confiança na segurança da criptografia. Talvez não possamos ter as duas coisas.

Uma piada cruel

Em 1994, Razborov e Rudich perceberam que haviam chegado a insights semelhantes e começaram a trabalhar juntos para combinar seus resultados. Eles primeiro observaram que todas as tentativas anteriores de provar P ≠ NP usando a complexidade do circuito adotaram a mesma estratégia geral: identificar uma propriedade especial de uma função booleana NP-completa e, em seguida, provar que nenhuma função fácil de calcular poderia compartilhar essa propriedade. Isso mostraria que a função NP-completa escolhida era realmente difícil de calcular, provando que P ≠ NP.

Sipser, Razborov e outros usaram essa mesma estratégia com sucesso para provar seus resultados mais limitados e, em todos os casos, a propriedade especial que os pesquisadores identificaram foi compartilhada pela maioria das funções booleanas. Razborov e Rudich cunharam o termo “prova natural” para se referir a este caso em que a propriedade foi amplamente compartilhada, simplesmente porque não havia alternativa conhecida. Se provas “não naturais” fossem possíveis, elas teriam que ser muito contra-intuitivas e merecedoras desse nome.

Razborov e Rudich provaram então seu principal resultado: uma prova natural de P ≠ NP exigiria uma compreensão muito abrangente de como as funções fáceis de calcular e difíceis de calcular diferem, e esse conhecimento também poderia alimentar um algoritmo rápido para identificar funções fáceis de calcular. -para calcular funções, mesmo que sejam superficialmente complicadas. Se os teóricos da complexidade tivessem conseguido uma prova natural de P ≠ NP, eles teriam descoberto uma maneira quase infalível de olhar para uma tabela verdade arbitrária e determinar se a função correspondente tinha alta ou baixa complexidade de circuito - um resultado muito mais forte e mais geral do que eles pretendiam provar.

“É quase impossível não conseguir mais do que esperava”, disse Carmosino.

É como se você tentasse verificar uma declaração específica, mas cada tentativa se transformasse em um projeto para um detector de mentiras de uso geral - pareceria bom demais para ser verdade. Para os teóricos da complexidade, o surpreendente poder das provas naturais também fez com que o sucesso parecesse menos provável. Mas se tal prova tivesse sido bem-sucedida, as consequências inesperadas seriam más notícias para a criptografia, devido à conexão entre a complexidade do circuito e a pseudo-aleatoriedade.

Para entender essa conexão, imagine olhar para a coluna de saída na tabela verdade de uma função booleana com muitas variáveis ​​de entrada e substituir cada “verdadeiro” por 1 e cada “falso” por 0:

Se a função booleana tiver alta complexidade de circuito, essa longa lista de saídas será, em princípio, indistinguível de uma sequência verdadeiramente aleatória de 0s e 1s - uma obtida pelo lançamento repetido de uma moeda, digamos. Mas se a função tiver baixa complexidade de circuito, a string deve ter uma descrição simples e sucinta, mesmo que pareça complicada. Isso o torna muito semelhante às strings pseudo-aleatórias usadas na criptografia, cuja descrição sucinta é a mensagem secreta enterrada naquela aparente aleatoriedade.

Portanto, o resultado de Razborov e Rudich mostrou que qualquer prova natural de P ≠ NP também produziria um algoritmo rápido que poderia distinguir strings pseudo-aleatórias contendo mensagens ocultas de strings verdadeiramente aleatórias. A criptografia segura seria impossível – exatamente o oposto do que os pesquisadores esperavam estabelecer ao provar que P ≠ NP.

Por outro lado, se a criptografia segura for possível, então as provas naturais não são uma estratégia viável para provar P ≠ NP — um pré-requisito para a criptografia segura. Em poucas palavras, essa é a barreira natural das provas. Parecia que os teóricos da complexidade estavam sendo alvo de uma piada cruel.

“Se você acredita em dureza, deve acreditar que é difícil provar dureza”, disse Kabanets.

No Metaverso

Essa conexão entre as implicações da conjectura P ≠ NP e a dificuldade de prová-la era intrigante, mas difícil de definir. Por um lado, a barreira das provas naturais bloqueou apenas uma abordagem para provar P ≠ NP. Por outro lado, vinculou a dificuldade de provar P ≠ NP não ao próprio P ≠ NP, mas à existência de criptografia segura — um problema intimamente relacionado, mas não exatamente equivalente. Para compreender verdadeiramente a ligação, os investigadores teriam de se sentir confortáveis ​​com a metacomplexidade.

“Existe essa intuição de que 'oh, porque P ≠ NP, é difícil provar que P ≠ NP'”, disse Williams. “Mas, para entender essa intuição, você precisa começar a pensar na tarefa de provar algo como P ≠ NP como um problema computacional.”

Foi isso que Kabanets fez como aluno de pós-graduação. Ele cresceu na Ucrânia e terminou seus estudos de graduação em ciência da computação dois anos após a queda da União Soviética. Na turbulência que se seguiu, ele teve poucas oportunidades de se dedicar aos tópicos teóricos que mais o interessavam.

“Eu queria fazer algo mais acadêmico”, lembrou Kabanets. “E eu também estava curioso para ver o mundo.” Ele se mudou para o Canadá para fazer pós-graduação, e foi lá que aprendeu sobre a barreira das provas naturais. Assim como Carmosino, Kabanets ficou encantado com o resultado. “Parecia muito profundo que você tivesse essa conexão”, disse ele.

Em 2000, no final de sua pós-graduação, ele descobriu que a barreira das provas naturais continuava surgindo em suas conversas com Jin-Yi Cai, um teórico da complexidade que estava visitando Toronto em um ano sabático na época. Eles começaram a ver a barreira não como um obstáculo, mas como um convite – uma oportunidade de investigar precisamente o quão difícil era provar que os problemas eram difíceis. O papel em que expuseram essa nova perspectiva se tornaria um dos primeiros trabalhos mais influentes no campo nascente da metacomplexidade.

O artigo de Kabanets e Cai destacou um problema computacional implícito na formulação de Razborov e Rudich da barreira de provas naturais: Dada a tabela verdade de uma função booleana, determine se ela tem alta ou baixa complexidade de circuito. Eles apelidaram isso de problema do tamanho mínimo do circuito, ou MCSP.

O MCSP é um problema de metacomplexidade por excelência: um problema computacional cujo assunto não é a teoria dos grafos ou outro tópico externo, mas a própria teoria da complexidade. Na verdade, é como uma versão quantitativa da questão que levou os teóricos da complexidade a enfrentar P versus NP usando a abordagem da complexidade do circuito na década de 1980: quais funções booleanas são difíceis de calcular e quais são fáceis?

“Se criássemos um algoritmo MCSP, seria uma forma de automatizar o que estamos fazendo na teoria da complexidade”, disse Impagliazzo. “Deveria pelo menos nos dar uma visão tremenda de como fazer melhor nosso trabalho.”

Os teóricos da complexidade não se preocupam com esse algoritmo mágico colocando-os fora do trabalho - eles não acham que exista, porque Razborov e Rudich mostraram que qualquer algoritmo desse tipo para distinguir tabelas-verdade de alta complexidade das de baixa complexidade tornaria a criptografia impossível. Isso significa que o MCSP é provavelmente um problema computacional difícil. Mas quão difícil é? É NP-completo, como o problema do caminho hamiltoniano e quase todos os outros problemas com os quais os pesquisadores lutaram na década de 1960?

Para problemas em NP, “quão difícil é?” geralmente é fácil de responder, mas o MCSP parecia ser um estranho estranho. “Temos muito poucos problemas 'flutuando' que não foram conectados a esta ilha de problemas NP-completos, embora pareçam ser difíceis”, disse Kabanets.

Kabanets sabia que ele e Cai não eram os primeiros a considerar o problema que eles apelidaram de MCSP. Os matemáticos soviéticos estudaram um problema muito semelhante no início da década de 1950, em uma tentativa inicial de entender a dificuldade intrínseca de diferentes problemas computacionais. Leonid Levin lutou com isso enquanto desenvolvia o que se tornaria a teoria da NP-completude no final dos anos 1960, mas não conseguiu provar que era NP-completo e publicou seu artigo seminal sem ela.

Depois disso, o problema atraiu pouca atenção por 30 anos, até que Kabanets e Cai notaram sua ligação com a barreira das provas naturais. Kabanets não esperava resolver a questão sozinho - em vez disso, ele queria explorar por que tinha sido tão difícil provar que esse problema aparentemente difícil sobre dureza computacional era realmente difícil.

“É, em certo sentido, meta-meta-complexidade”, disse Rahul Santhanam, um teórico da complexidade da Universidade de Oxford.

Mas era dureza o tempo todo ou havia pelo menos alguma maneira de entender por que os pesquisadores não conseguiram provar que o MCSP era NP-completo? Kabanets descobriu que, sim, havia uma razão: a dificuldade de entender a complexidade do circuito atua como uma barreira para qualquer estratégia conhecida para provar a NP-completude do MCSP - um problema que é sobre a dificuldade de entender a complexidade do circuito. A lógica distorcida e autodestrutiva da barreira das provas naturais parecia inevitável.

Também é possível que MCSP não seja NP-completo, mas isso também parece improvável - já se sabe que certas variantes mais simples do problema são NP-completas.

“Simplesmente não temos um bom lugar para colocá-lo que o relacione diretamente com todos os outros problemas que estudamos”, disse Impagliazzo.

Kabanets havia iluminado o comportamento estranho do MCSP, mas ele não sabia como fazer mais progressos. A pesquisa de meta-complexidade diminuiu para um gotejamento. Ele floresceria novamente 16 anos depois, quando os pesquisadores descobriram uma conexão surpreendente com outra questão fundamental: quão difícil é resolver problemas se você só se preocupa em obter a resposta certa na maioria das vezes?

Guerra dos Mundos

Para problemas cotidianos, as respostas que funcionam na maioria das vezes costumam ser boas o suficiente. Planejamos nossos deslocamentos para padrões de tráfego típicos, por exemplo, não para os piores cenários.

A maioria dos teóricos da complexidade é mais difícil de satisfazer: eles só se contentam em declarar um problema fácil se puderem encontrar um algoritmo rápido que obtenha a resposta certa em todas as entradas possíveis. Essa abordagem padrão classifica os problemas de acordo com o que os pesquisadores chamam de complexidade do “pior caso”. Mas há também uma teoria da complexidade do “caso médio”, na qual os problemas são considerados fáceis se houver um algoritmo rápido que obtenha a resposta certa na maioria das entradas.

A distinção é importante para os criptógrafos. Imagine um problema computacional fácil de resolver para quase todas as entradas, exceto para alguns casos difíceis em que o melhor algoritmo falha. A teoria da complexidade do pior caso considera isso um problema difícil, mas para a criptografia é inútil: se apenas algumas de suas mensagens são difíceis de decifrar, qual é o objetivo?

Na verdade, foi Levin quem iniciou o estudo rigoroso da complexidade do caso médio, uma década depois de seu trabalho pioneiro sobre NP-completude. Nos anos seguintes, ele entrou em conflito com as autoridades soviéticas - ele era um encrenqueiro irreverente que ocasionalmente minava as atividades patrióticas de seu grupo de jovens do Partido Comunista. Em 1972, seu doutorado foi negado por razões explicitamente políticas.

“Para ter sucesso na União Soviética como um jovem pesquisador, você não precisa ser muito teimoso, e é difícil imaginar que Leonid não o seja”, disse Impagliazzo.

Levin emigrou para os Estados Unidos em 1978 e, em meados da década de 1980, voltou sua atenção para a complexidade do caso médio. Ele começou a trabalhar com outros para desenvolver ainda mais a teoria, incluindo Impagliazzo, um estudante de pós-graduação na época. Mas, mesmo à medida que avançavam, Impagliazzo descobriu que os pesquisadores frequentemente conversavam entre si. Ele queria colocar todos na mesma página, e não ajudou o fato de os papéis de Levin serem notoriamente sucintos - aquele que iniciou o campo de complexidade de caso médio tinha menos de duas páginas.

“Eu ia fazer uma tradução do trabalho de Leonid para termos técnicos mais acessíveis”, disse Impagliazzo. Ele decidiu começar com uma visão geral curta e divertida do quadro geral antes de mergulhar na matemática. “Isso meio que assumiu o papel, e é a única parte que alguém se lembra de qualquer maneira.”

A papel, publicado em 1995, tornou-se um clássico instantâneo. Impagliazzo cunhou nomes extravagantes para cinco mundos distinguido por diferentes graus de dureza computacional e diferentes capacidades criptográficas. Vivemos em um desses mundos, mas não sabemos qual.

Desde que o artigo de Impagliazzo apareceu, os pesquisadores sonham em eliminar partes de seu multiverso em miniatura – estreitando o espaço de possibilidades ao provar que alguns dos mundos não são possíveis, afinal. Dois mundos são alvos especialmente tentadores: aqueles onde a criptografia é impossível mesmo que P ≠ NP.

Em um desses mundos, chamado Heurística, todos os problemas NP-completos são fáceis de resolver na maioria das entradas, mas algoritmos rápidos ocasionalmente cometem erros, então esses problemas ainda são considerados difíceis pelos padrões da teoria da complexidade do pior caso. Este é o mundo em que a criptografia é impossível porque quase todos os códigos são facilmente decifrados. No outro mundo, chamado Pessiland, a criptografia é impossível por um motivo diferente: todo problema é difícil no sentido do caso médio, mas criptografar uma mensagem a torna ilegível até mesmo para o destinatário pretendido.

Estes dois mundos revelam-se intimamente ligados a problemas de meta-complexidade - em particular, o destino da Heurística está ligado à antiga questão de saber se o MCSP é NP-completo. A questão que fascinou Kabanets e deixou Levin perplexo há tanto tempo não é mera curiosidade: há um mundo inteiro em jogo.

Para descartar a Heurística, os pesquisadores teriam que reduzir a distinção entre a complexidade do pior caso e da complexidade do caso médio - ou seja, eles teriam que provar que qualquer algoritmo hipotético que resolva um problema NP-completo corretamente na maioria das entradas pode realmente resolvê-lo em todos os casos. Esse tipo de conexão, chamado de redução do pior caso para o caso médio, é conhecido por existir para certos problemas, mas nenhum deles é NP-completo, então esses resultados não implicam em nada mais geral. A eliminação da Heurística levaria os criptógrafos a meio caminho para realizar o sonho da criptografia segura com base na suposição única de que P ≠ NP.

Mas destruir um mundo não é tarefa fácil. Em 2003, dois teóricos da complexidade mostrou que as abordagens existentes para provar reduções do pior caso para o caso médio para problemas NP-completos conhecidos implicariam consequências estranhas, sugerindo que tais provas provavelmente não são possíveis.

Os pesquisadores teriam que encontrar outra abordagem e agora acham que o MCSP pode ser exatamente o problema de que precisam. Mas isso não ficaria claro por mais de uma década. O primeiro vislumbre da ligação surgiu do persistente fascínio de Marco Carmosino pela barreira das provas naturais.

Carmosino encontrou pela primeira vez a pesquisa de metacomplexidade como estudante de pós-graduação por meio de um papel 2013 por Kabanets e quatro outros pesquisadores, que desenvolveram ainda mais a abordagem da barreira de provas naturais que Kabanets foi pioneira mais de uma década antes. Isso apenas reforçou sua convicção de que ainda havia mais a aprender com o artigo clássico de Razborov e Rudich.

“Na época, eu estava obcecado com aquele jornal”, disse Carmosino. "Nada mudou."

A obsessão finalmente deu frutos durante uma visita a um workshop de um semestre na Universidade da Califórnia, em Berkeley, onde passou a maior parte do tempo conversando com Impagliazzo, Kabanets e Antonina Kolokolova, um teórico da complexidade da Memorial University of Newfoundland que colaborou com Kabanets no artigo de 2013. Carmosino já tinha trabalhado com os três uma vez e essa colaboração bem sucedida deu-lhe a confiança necessária para os encher de perguntas sobre o tema que mais o fascinava.

“Ele estava incomodando as pessoas no bom sentido”, lembrou Kabanets.

A princípio, Carmosino teve novas ideias para provar a NP-completude para a versão do MCSP que apareceu no artigo de Razborov e Rudich sobre a barreira de provas naturais. Mas essas ideias não deram certo. Em vez disso, uma observação improvisada de Impagliazzo fez os quatro pesquisadores perceberem que a barreira das provas naturais poderia produzir algoritmos mais poderosos do que qualquer um havia imaginado – havia um mapa secreto gravado no bloqueio.

Em um artigo do papel 2016, os quatro pesquisadores provaram que um certo tipo de algoritmo MCSP de caso médio poderia ser usado para construir um algoritmo de pior caso para identificar padrões ocultos em sequências de dígitos de aparência aleatória – uma tarefa que os cientistas da computação chamam de “aprendizado”. É um resultado surpreendente porque o aprendizado intuitivamente parece mais difícil do que a tarefa de classificação binária – alta ou baixa complexidade – realizada por um algoritmo MCSP. E, surpreendentemente, associou a complexidade do pior caso de uma tarefa à complexidade do caso médio da outra.

“Não era óbvio que tal conexão existiria”, disse Impagliazzo.

Um algoritmo rápido para MCSP é puramente hipotético para circuitos booleanos gerais: não pode existir a menos que MCSP se torne um problema computacional fácil, apesar de todas as evidências em contrário, e isso significa que o algoritmo de aprendizado implícito no artigo dos quatro pesquisadores é igualmente hipotética.

Mas para algumas versões mais simples do MCSP – distinguindo tabelas de verdade de alta complexidade de baixa complexidade quando há restrições específicas nos circuitos – algoritmos rápidos são conhecidos há muitos anos. O artigo de Carmosino, Impagliazzo, Kabanets e Kolokolova mostrou que esses algoritmos poderiam ser transformados em algoritmos de aprendizado igualmente restritos, mas ainda mais poderosos do que qualquer outro que os pesquisadores haviam entendido anteriormente em um nível teórico tão rigoroso.

“De alguma forma, seu sabor auto-referencial permite que você faça coisas que aparentemente você não pode fazer com problemas mais comuns”, disse Ilango.

O resultado chamou a atenção de teóricos da complexidade que trabalham em outros tópicos. Foi também uma prévia de outras conexões entre metacomplexidade e complexidade de caso médio que surgiriam nos próximos anos.

Acima de tudo, foi uma prova de quão longe os pesquisadores podem chegar fazendo perguntas simples sobre barreiras que a princípio parecem apenas obstruir seu progresso.

“Esse tipo de dualidade é um tema ao longo dos últimos 30 ou 40 anos de complexidade”, disse Impagliazzo. “Os obstáculos são muitas vezes as oportunidades.”

Crédito parcial

O progresso só acelerou nos anos desde que Carmosino e seus colegas publicaram seu artigo.

“Coisas novas estão acontecendo”, disse Kolokolova. “Existem muitos pesquisadores juniores muito, muito brilhantes.”

Ilango é um desses jovens pesquisadores - em seus primeiros três anos de pós-graduação, ele atacou o assustador problema em aberto de provar que o MCSP é NP-completo usando uma estratégia em duas frentes: provar a completude NP para mais simples versões do MCSP, como pesquisadores de complexidade de circuitos fizeram ao atacar P versus NP na década de 1980, ao mesmo tempo em que provavam a completude NP para versões mais complicadas, que intuitivamente parecem mais difíceis e, portanto, talvez sejam mais fáceis de provar serem difíceis.

Ilango credita seu interesse na meta-complexidade a Eric Allender, um teórico da complexidade da Universidade Rutgers e um dos poucos pesquisadores que continuou trabalhando na metacomplexidade na década de 2000 e no início de 2010. “Seu entusiasmo era contagiante”, disse Ilango.

Outro jovem pesquisador inspirado por Allender é Shuichi Hirahara, agora professor do Instituto Nacional de Informática em Tóquio. Ainda estudante de pós-graduação em 2018, Hirahara revelou a verdadeira extensão da relação entre metacomplexidade e complexidade de caso médio que Carmosino e seus coautores haviam descoberto. Esses quatro pesquisadores encontraram uma conexão entre a complexidade de caso médio de um problema – MCSP – e a complexidade de pior caso de outro – aprendizado booleano. Hirahara desenvolveu suas técnicas ainda mais para derivar uma redução do pior caso para o caso médio para MCSP. Seu resultado implica que um algoritmo MCSP de caso médio hipotético como aquele que Carmosino e seus colegas consideraram seria realmente poderoso o suficiente para resolver uma versão ligeiramente diferente do MCSP sem cometer nenhum erro.

O resultado de Hirahara é empolgante porque muitos pesquisadores suspeitam que o MCSP é NP-completo, ao contrário de todos os outros problemas para os quais são conhecidas reduções do pior caso para o caso médio. Se eles puderem estender os resultados de Hirahara para cobrir todos os algoritmos de caso médio e provar que MCSP é NP-completo, isso provaria que não vivemos na Heurística.

“Isso seria realmente um resultado de abalar a terra”, disse Santhanam.

Provar que o MCSP é NP-completo pode parecer uma tarefa difícil – afinal, a questão está em aberto há mais de 50 anos. Mas depois de um avanço no ano passado por Hirahara, os pesquisadores estão agora muito mais próximos do que qualquer um esperaria alguns anos atrás.

Hirahara provou a NP-completude para uma variante do problema chamada MCSP parcial, na qual você ignora certas entradas em cada tabela verdade. Sua prova baseou-se em métodos desenvolvidos por Ilango para mostrar que o MCSP parcial era equivalente a um problema aparentemente não relacionado envolvendo uma técnica criptográfica chamada compartilhamento secreto. Essa é uma forma de dividir uma mensagem criptografada entre várias pessoas, de modo que ela só possa ser decodificada se uma certa fração delas trabalhar em conjunto.

Para qualquer aplicação real em criptografia, você gostaria de saber essa fração com antecedência, mas com a ajuda de truques criptográficos extras, você pode construir um cenário frustrante no qual é difícil descobrir quantas pessoas precisam cooperar. Hirahara encontrou uma maneira de provar que esse problema criptográfico artificial era NP-completo e então mostrou que a prova implicava a NP-completude do MCSP parcial também.

Esse resultado energizou os pesquisadores em metacomplexidade ainda mais do que o trabalho anterior de Hirahara, e outros pesquisadores também notaram - o teórico da complexidade e blogueiro Lance Fortnow o apelidou de resultado do ano. Isso porque lidar com essas versões de “função parcial” de problemas computacionais tem sido uma etapa intermediária chave em outras provas de NP-completude.

“É um trabalho incrível”, disse Williams. “Todos pensaram que esses problemas parciais eram aproximadamente a mesma dificuldade que o problema completo.”

Restam impedimentos para provar a NP-completude para a versão completa do MCSP. Mas nenhum é o tipo de barreira que sugere que um kit de ferramentas totalmente novo é necessário - pode ser apenas uma questão de encontrar o caminho certo para combinar técnicas conhecidas. Uma prova finalmente resolveria o status de um dos poucos problemas que resistiram à classificação desde que a teoria da complexidade existe. Por e-mail, Levin escreveu: “Me humilharia mostrar que fui estúpido por não ter conseguido ver :-)”.

As peças que faltam

O MCSP nem é o único problema de metacomplexidade que estimulou um grande avanço. Em 2020, o criptógrafo da Cornell Tech Passe Rafael e seu aluno de pós-graduação Yan Yi Liu descobriu uma conexão entre um problema de metacomplexidade diferente e um protocolo criptográfico fundamental que define a fronteira entre Heuristica e Pessiland, o pior dos mundos de Impagliazzo (onde problemas NP-completos são difíceis no sentido do caso médio, mas a criptografia ainda é impossível). Isso faz com que o problema que estudaram seja o principal candidato para um ataque à Pessilândia, e a sua trabalho mais recente indica que poderia funcionar contra o Heuristica também.

“Faltam diferentes peças do quebra-cabeça”, disse Pass. “Para mim é simplesmente mágico que esses campos estejam tão intimamente conectados.”

Hirahara adverte que os desafios ainda aguardam os pesquisadores que pretendem selecionar os mundos que Impagliazzo conjurou há 30 anos. “Gostaria de dizer que em algum momento Heuristica e Pessiland serão descartados, mas não tenho certeza de quão perto estamos”, disse ele.

Muitos pesquisadores esperam que a maior dificuldade seja preencher uma lacuna aparentemente inócua entre dois modelos diferentes de complexidade de caso médio. Os criptógrafos geralmente estudam algoritmos de caso médio que cometem erros em ambas as direções, ocasionalmente rotulando strings aleatórias como pseudo-aleatórias e vice-versa. As reduções do pior caso para o caso médio de Hirahara, enquanto isso, funcionam para algoritmos de caso médio que cometem apenas o primeiro tipo de erro. Distinções sutis como essa podem fazer muita diferença na teoria da complexidade. Mas, apesar desse obstáculo e de muitos outros, Allender não pode deixar de mostrar uma nota de otimismo cauteloso.

“Tento não acreditar muito porque há um histórico bem estabelecido de que nada funciona”, disse ele. “Mas estamos vendo muitos desenvolvimentos realmente interessantes – maneiras de superar coisas que pareciam barreiras.”

Se há uma lição que os pesquisadores aprenderam com suas lutas para responder à questão P versus NP – ou mesmo apenas entendê-la – é que a teoria da complexidade é em si complexa. Mas esse desafio é precisamente o que torna a busca tão gratificante.

“Na verdade, é ótimo que seja tão difícil”, disse Carmosino. “Eu nunca vou ficar entediado.”

Nota do editor: Scott Aaronson é membro do Revista Quanta'S conselho consultivo.