Quão difícil é provar que os problemas são difíceis de resolver? Os teóricos da metacomplexidade têm feito perguntas como essa há décadas. Uma série de resultados recentes começou a fornecer respostas.
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 teórico cientista da computação 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 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 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 onde uma possível prova deve 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, aluno de pós-graduação do MIT que produziu alguns dos resultados recentes mais empolgantes no campo.
Ao estudar essas questões introspectivas, os pesquisadores aprenderam que a dificuldade de provar a dureza computacional está intimamente ligada a questões fundamentais que podem parecer a princípio não relacionadas. Quão difícil é identificar padrões ocultos em dados aparentemente aleatórios? E se existem problemas realmente difíceis, com que frequência eles são difíceis?
“Ficou claro que a metacomplexidade está perto do cerne das coisas”, disse Scott Aaronson, teórico da complexidade da Universidade do Texas, em 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 Valentine Kabanets, um teórico da complexidade da Universidade Simon Fraser, no Canadá, e “você não tem ideia de onde está indo”.
Desconhecidos conhecidos
O problema P versus NP deve seu nome medíocre ao hábito dos teóricos da complexidade de classificar problemas computacionais em amplas “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 coleção crescente 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 resolver enormes quebra-cabeças de sudoku, otimizar rotas de navegação globais, quebrar criptografia de última geração e automatizar as provas de teoremas matemáticos. Se P – NP, então muitos problemas computacionais que são solucionáveis em princípio, na prática, permanecerão para sempre fora de 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, 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 encaixaria nesse modelo. Ele então usou métodos autorreferenciais como o de Gödel para provar a existência de declarações indecidíveis – ou, de forma equivalente, 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 computado. Mas, à medida que os computadores evoluíram de abstrações teóricas para máquinas reais, os pesquisadores perceberam que a simples distinção de Turing entre problemas solucionáveis e insolúveis deixava muitas perguntas 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 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 até o 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 fica fora 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 que até mesmo os melhores algoritmos que os pesquisadores descobriram não consigam encontrar um caminho “em um período de tempo razoável”, disse Russell Impagliazzo, teórico da complexidade da Universidade da Califórnia, em San Diego. “E por ‘quantidade de tempo razoável’, quero dizer ‘antes que o universo acabe’.”
O problema do caminho hamiltoniano tem outra propriedade interessante. Se alguém afirma ter encontrado um caminho hamiltoniano em um gráfico especí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 grande assimetria: 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 esse caráter assimétrico. De fato, um problema muito semelhante a 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 específico 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.
Mais ou menos na mesma época, um aluno de graduação da União Soviética chamado Leonid Levin provou um resultado semelhante, exceto pelo fato de ter identificado vários problemas universais diferentes. Além disso, o teórico da complexidade americano Richard Karp provou que a propriedade de universalidade identificada por Cook (e Levin, embora Karp e Cook não conhecessem o trabalho de Levin até 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 em um 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 eles o encontrarão tão cedo: os teóricos da complexidade ocasionalmente descobriram 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 passo. “É 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.”
II.Obstáculos
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: ‘Uau, 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, pode: chama-se pós-graduação'”, disse Carmosino. Depois de obter seu mestrado, ele se mudou para San Diego em 2012 para fazer um doutorado supervisionado por Impagliazzo.
O principal objetivo de Carmosino, a princípio, era entender melhor um artigo histórico de duas décadas antes que havia capturado sua imaginação. Esse artigo, dos teóricos da complexidade Alexander 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 – o colapso completo da criptografia – que os pesquisadores consideravam como 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 a trilha da barreira das provas naturais até a metacomplexidade, teremos que voltar para onde deixamos os pesquisadores na década de 1970, quando eles começaram a enfrentar o problema P versus NP. O que tornou tão difícil provar que os problemas são difíceis?
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 descobriram 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 na obra de Claude Shannon, contemporâneo de Turing.
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. Em sua dissertação de mestrado, Shannon mostrou como circuitos feitos de interruptores eletromecânicos poderiam 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? É 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”, mesmo que 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, 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.
Essa foi a estratégia que a maioria dos teóricos da complexidade perseguiu na década de 1980. E as chances estavam do lado deles. Shannon 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?
Crypto Bros
No início, o progresso foi rápido. Em 1981, Sipser e dois colaboradores provaram que uma certa função booleana era definitivamente difícil de calcular se eles usassem circuitos com certas restrições sobre como as portas poderiam ser arranjadas.
“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 ao esforço acidentalmente ao resolver 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 determinada função era difícil de calcular usando tais circuitos, não importando como as portas estivessem organizadas – 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 golpe, e vamos conseguir”, disse Razborov. Mas não foi isso que aconteceu. O próprio Razborov provou que seu método falharia se 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 desaparecido.
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 amplamente usados hoje 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 auto-referenciais 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 parado, ele começou a perceber que os dois assuntos não estavam tão distantes, afinal. A estratégia que os pesquisadores adotaram em suas tentativas de provar que P – NP tinha um caráter autodestrutivo que lembrava a famosa proposição de Gödel “esta afirmação é improvável” – e a criptografia poderia ajudar a explicar o 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 então provaram seu principal resultado: uma prova natural de P – NP exigiria uma compreensão muito abrangente de como 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. -to-compute 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 de verdade arbitrária e determinar se a função correspondente tinha alta ou baixa complexidade de circuito – um resultado muito mais forte e geral do que eles se propuseram a provar.
“Você quase não pode deixar de receber 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 propósito geral – parece 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 das 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 é 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. Essa é a barreira de provas naturais em poucas palavras. Parecia que os teóricos da complexidade estavam recebendo uma piada cruel.
“Se você acredita em dureza, deve acreditar que é difícil provar a 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 a P – NP em si, mas à existência de criptografia segura – um problema intimamente relacionado, mas não exatamente equivalente. Para realmente entender a conexão, os pesquisadores teriam que se familiarizar 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 estudante 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 seu tempo na 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 artigo 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 ‘flutuantes’ que não foram conectados a esta ilha de problemas NP-completos, mesmo que pareçam difíceis”, disse Kabanets.
Kabanets sabia que ele e Cai não foram os primeiros a considerar o problema que 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, 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 funciona 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 o MCSP não seja NP-completo, mas isso também parece improvável – certas variantes mais simples do problema já são conhecidas como 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 também existe uma teoria da complexidade do “caso médio”, na qual os problemas são considerados fáceis se houver um algoritmo rápido que obtém 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 ponto?
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 ser bem-sucedido 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 artigos de Levin serem notoriamente sucintos – aquele que iniciou o campo da complexidade do 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.”
O jornal, publicado em 1995, tornou-se um clássico instantâneo. Impagliazzo cunhou nomes extravagantes para cinco mundos distinguidos 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.
Esses dois mundos acabam por estar intimamente ligados a problemas de meta-complexidade – em particular, o destino da Heurística está ligado à questão de longa data sobre 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 é pouca coisa. Em 2003, dois teóricos da complexidade mostraram 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.
III.Oportunidades
Carmosino encontrou pela primeira vez a pesquisa de metacomplexidade como estudante de pós-graduação por meio de um artigo de 2013 de Kabanets e quatro outros pesquisadores, que desenvolveu ainda mais a abordagem da barreira de provas naturais que Kabanets havia pioneiro 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 por 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, uma teórica da complexidade da Memorial University of Newfoundland que colaborou com Kabanets no jornal de 2013. Carmosino já havia trabalhado com os três uma vez, e essa colaboração bem-sucedida deu-lhe confiança para enchê-los 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 de 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 impressionante porque aprender intuitivamente parece mais difícil do que a tarefa de classificação binária – alta complexidade ou baixa complexidade – realizada por um algoritmo MCSP. E, surpreendentemente, vinculou 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 MCSP NP-completo usando uma estratégia em duas frentes: provar NP-completude para versões mais simples de MCSP, como pesquisadores de complexidade de circuito fez ao atacar P versus NP na década de 1980, ao mesmo tempo em que provou a completude NP para versões mais complicadas, que intuitivamente parecem mais difíceis e, portanto, talvez sejam mais fáceis de provar difíceis.
Ilango credita seu interesse na metacomplexidade a Eric Allender, um teórico da complexidade da Rutgers University e um dos poucos pesquisadores que continuaram trabalhando na metacomplexidade nos anos 2000 e início dos anos 2010. “Seu entusiasmo era contagiante”, disse Ilango.
Outro jovem pesquisador inspirado por Allender é Shuichi Hirahara, hoje professor do Instituto Nacional de Informática de 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 ainda mais suas técnicas 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 uma descoberta 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 meta-complexidade 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 o resultado do ano. Isso ocorre 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 meta-complexidade que estimulou um grande avanço. Em 2020, o criptógrafo da Cornell Tech Rafael Pass e seu aluno de pós-graduação Yanyi Liu descobriram 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 torna o problema que eles estudaram um candidato principal para um ataque a Pessiland, e seu trabalho mais recente indica que também pode funcionar contra a Heurística.
“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 demonstrar um otimismo cauteloso.
“Eu tento não me deixar ser muito crente porque há um histórico bem estabelecido de que nada funciona”, disse ele. “Mas estamos vendo muitos desenvolvimentos realmente empolgantes – 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.”
Publicado em 22/08/2023 03h01
Artigo original: