Um mistério da teoria dos números no qual a humanidade está presa há décadas — a IA o resolveu em apenas 8 páginas?
Nos últimos dois dias, toda a comunidade matemática e os círculos da ciência da computação ficaram em enorme choque.
Em 18 de outubro, as palavras do teórico dos números da Universidade de Stanford, Jared Duker Lichtman, no X incendiaram instantaneamente toda a internet —
"A existência de tal prova sugere fortemente que P≠NP."
O gatilho para essa declaração foi a espantosa folha de respostas recém-entregue por um modelo interno da OpenAI — uma prova de que "não existe zero de Landau-Siegel".
Esse problema-chave da teoria analítica dos números, que está travado há décadas, é amplamente reconhecido pela comunidade acadêmica como extremamente difícil.
Como resultado, não apenas a OpenAI o resolveu, mas a prova original tinha na verdade apenas 8 páginas!
Desdobramentos ainda mais empolgantes se seguiram. Matemáticos de ponta rapidamente deram continuidade:
Bill Banks, da Universidade do Missouri, primeiro escreveu uma detalhada análise de 19 páginas;
Imediatamente depois, Bryce Kerr usou extensões biquadráticas
e os resultados clássicos de Masser para comprimir a prova para 6 páginas;
Posteriormente, o professor Ben Green, da Universidade de Oxford, reduziu-a novamente, dando diretamente a versão final de 5 páginas!
De décadas de insolubilidade sem esperança para apenas 5 páginas. O professor Abhishek Saha, da Queen Mary University of London, levantou uma questão que faz refletir:
Se esse problema pode ser provado em apenas 5 páginas, por que os matemáticos o deixaram passar por décadas?
Encontrá-lo é como escalar até o céu, verificá-lo é como beber água
Por que uma prova de teoria dos números de 5 páginas faria um professor de Stanford pensar diretamente no Santo Graal da ciência da computação — P vs NP?
A razão é simples.
Uma prova de 5 páginas pode ser lida e verificada por qualquer especialista em algumas horas; mas, por essas 5 páginas, as mentes mais brilhantes da humanidade lutaram por décadas.
"Encontrar é extremamente difícil, verificar é extremamente fácil." Essas oito palavras são precisamente a intuição subjacente de P≠NP!
Na seção de comentários, o pesquisador da Anthropic Joshua Batson apontou de forma incisiva —
O "óbvio" dos matemáticos é sempre relativo. Os fatos provaram que muitos problemas não resolvidos (em relação à IA) são todos óbvios!
Por trás da piada há uma questão extremamente séria: quando a IA entrega mais de 700 manuscritos matemáticos em poucas semanas, o problema do milênio P vs NP também está chegando?
Três altos muros que mantêm a humanidade bloqueada por cinquenta anos
Explique P vs NP em uma frase: todos os problemas cujas respostas podem ser rapidamente verificadas são também problemas cujas respostas podem ser rapidamente computadas?
P é o conjunto de problemas que "podem ser resolvidos rapidamente", e NP é o conjunto de problemas que "podem ser verificados rapidamente".
Sudoku, agendamento de aulas e quebra de senhas pertencem todos a NP: dê a você a resposta, e você pode verificar se está certa ou errada em um segundo; mas para encontrá-la do zero, você só pode fazer algo próximo de uma busca exaustiva.
Se P=NP, a criptografia moderna entraria em colapso instantaneamente, as finanças globais ficariam completamente expostas, mas todos os problemas complexos teriam um atalho definitivo;
Se P≠NP, significa que o universo contém problemas que essencialmente não podem ter atalho.
Este problema foi proposto em 1971, com um prêmio de 1 milhão de dólares. A grande maioria dos cientistas acredita que P≠NP, mas por mais de cinquenta anos ninguém conseguiu prová-lo.
Onde está a dificuldade? Porque a humanidade não apenas falhou em encontrar a chave, mas provou que as ferramentas de arrombamento existentes estão fadadas a ser ineficazes.
Estas são as famosas três "barreiras":
1. A barreira da relativização (1975): métodos clássicos que dependem de simulação e diagonalização simplesmente não conseguem resolvê-lo;
2. A barreira das provas naturais (1994): a maioria das abordagens de prova para limites inferiores de circuitos, se pudessem provar P≠NP, incidentalmente quebrariam geradores de números pseudorrandômicos, levando a uma autocontradição;
3. A barreira da algebrização (2008): métodos aprimorados combinados com técnicas algébricas também foram provados ter poder de fogo insuficiente.
Em junho deste ano, o teórico da complexidade Lance Fortnow declarou pessimistamente: atualmente, a humanidade não tem sequer uma rota de ataque viável.
Ele sugeriu que os desafiadores primeiro provassem um problema muito mais simples, como "SAT não tem algoritmo de tempo quadrático", e então acrescentou um golpe final: "Você também não terá sucesso aí."
Este é o oponente que a IA tem de enfrentar.
719 manuscritos bombardeiam as muralhas, um prodígio de 9 anos chega bem perto
Diante de muralhas de bronze e ferro, a IA lançou diretamente um ataque de saturação.
Em 6 de outubro, a OpenAI publicou 722 manuscritos de uma só vez no GitHub (3 foram retirados no dia seguinte), classificados em 372 famílias de resultados.
O modelo interno tentou cerca de 4.000 problemas abertos, com uma média de apenas cerca de 3 horas de computação do ChatGPT Pro por problema.
Entre eles, a ciência da computação teórica representou 40 famílias. Embora não tenha resolvido diretamente P vs NP, vários artigos aterrissaram precisamente nas estradas principais que levam a ele.
Em junho deste ano, o teórico da complexidade Lance Fortnow escreveu: além da simulação, não temos maneira de lidar com algoritmos gerais de tempo polinomial; complexidade de circuitos, complexidade de provas, geometria algébrica e outras rotas estão todas presas muito abaixo do poder total do tempo polinomial. Sua conclusão foi que atualmente não há sequer uma rota de ataque viável. Coincidentemente, os seis resultados da OpenAI desta vez plantaram uma bandeira em cada uma delas.
Família nº 112 (limites inferiores de circuitos de profundidade 3): A rota mais promissora para provar P vs NP é provar que algum problema NP requer "circuitos de tamanho superpolinomial". A humanidade há muito está presa em
sobre limites inferiores explícitos para circuitos de profundidade 3; desta vez, a IA cruzou diretamente esse limiar.
Família nº 102 (Conjectura dos Jogos Únicos, UGC): Provou esta conjectura central proposta por Subhash Khot em 2002 (incluindo verificação parcial em Lean). Está intimamente adjacente a P vs NP e fortalece enormemente os limites de inaproximabilidade de muitos problemas de otimização NP-difíceis.
Algoritmos fundamentais e desrandomização: Alcançou a desrandomização completa do espaço logarítmico randomizado (L=RL=BPL); comprimiu o expoente da multiplicação de matrizes para
; a multiplicação de inteiros e a DFT caíram abaixo de
tempo.
Em torno da Família nº 102, a "Conjectura dos Jogos Únicos", também houve um episódio comovente.
Dana Moshkovitz, esposa do famoso acadêmico Scott Aaronson, dedicou toda a sua carreira a esta conjectura. Na noite do lançamento, o filho de 9 anos deles correu para zombar da mãe:
"Ouvi dizer que um robô resolveu o problema que você pesquisa a vida inteira!"
A Quanta Magazine também divulgou que a equipe de Dor Minzer, do MIT, após ouvir rumores sobre a OpenAI em 11 de setembro, correu para publicar sua própria prova de uma variante relacionada antes da publicação da OpenAI, para não ser superada por uma máquina.
Os matemáticos humanos já começaram a correr contra a IA.
Grandes Nomes Jogam Água Fria: Cidade Externa Tomada, Portão da Cidade Intacto
No entanto, os especialistas que mais conhecem a área são os mais calmos.
Lance Fortnow publicou um artigo no dia seguinte apontando: a taxa de resolução da IA para problemas dados é inferior a 10%, e nenhum desses resultados nos aproxima de resolver P vs NP.
Embora Scott Aaronson tenha chamado 6 de outubro de "um dos dias mais importantes da história da matemática", ele também apontou: a lista não apenas carece de P≠NP, mas também carece de problemas difíceis "menores" como P=BPP — claramente não porque ninguém tentou.
Ele revelou no podcast: a OpenAI e a Anthropic estão usando seus modelos internos mais poderosos para correr em direção a decifrar P vs NP, mas nenhuma delas conseguiu até agora.
Olhando com calma, ainda existem quatro grandes obstáculos difíceis antes de um avanço:
1. A verificação está longe de ser completa: apenas cerca de 42% vêm com provas formalizadas em Lean, e o restante depende inteiramente de trabalho manual. Aaronson admite que quase nenhum humano realmente entendeu qualquer uma dessas longas provas.
2. A legibilidade é extremamente ruim: Moshkovitz comentou que a única prova de jogo feita por IA foi escrita "tão mal que é impossível entender sem a ajuda da IA".
3. O Lean não é onipotente: as máquinas só podem garantir que o raciocínio está correto, mas não podem garantir que as definições formalizadas sejam completamente consistentes com o problema original, nem podem julgar se o resultado é importante.
4. A rota central permanece em branco: o que a IA rompeu foram circuitos de profundidade 3 e circuitos algébricos, enquanto os "limites inferiores gerais de circuitos booleanos" que poderiam implicar P≠NP permanecem não escritos.
O Paradoxo Final: A IA é a Prova Viva de que P≠NP?
Já que o portão da cidade não foi rompido, por que ainda dizer que "a IA está se aproximando"?
Porque três sinais já são incomparavelmente claros.
Primeiro, a "dificuldade" dos problemas difíceis foi reprecificada. A prova de 5 páginas do zero de Siegel mostra que o que falta em alguns becos sem saída é o único passo que ninguém pensou. Quantas conjecturas estão a apenas uma camada de papel de janela de distância? Ninguém tem certeza.
Segundo, as posições periféricas estão florescendo por toda parte. Jogos únicos, limites inferiores de circuitos, desrandomização, multiplicação de matrizes... esses marcos em posições ao redor foram intensivamente conquistados pela IA, e a direção principal mais cedo ou mais tarde será rompida.
Terceiro, escala e velocidade não estão em uma ordem de magnitude humana. 4.000 problemas, com média de 3 horas cada. Quando os principais laboratórios apontam a próxima geração de seu poder computacional mais forte diretamente para P vs NP, o acúmulo quantitativo tem alta probabilidade de desencadear uma mudança qualitativa.
Quanto ao resultado final, divergências interessantes de apostas até surgiram no meio acadêmico.
Aaronson ainda aposta pesado em P≠NP; mas alguns estudiosos acreditam que, se a IA realmente puder romper, a resposta provavelmente será P=NP — porque fazer a IA buscar um algoritmo inteligente é muito mais fácil de imaginar do que usar a matemática existente para provar o "impossível".
No entanto, a parte mais intrigante e bem-humorada de tudo isso é —
Quanto mais poderosa a IA se torna, mais ela mesma se parece com uma prova viva de P≠NP.
Ela consome poder computacional massivo para "buscar" provas, enquanto os humanos gastam algumas horas para "verificar" os resultados.
Se um dia a IA realmente queimar seu poder computacional e provar P≠NP, essa será a mais perfeita autoprova desse problema do milênio.
Este artigo vem da conta pública do WeChat "Xinzhiyuan", autor: ASI Revelation
