Um olhar para a matemática que a OpenAI afirma computar transformadas de Fourier mais rápido
A recente afirmação da OpenAI de um algoritmo mais rápido que FFT para transformadas discretas de Fourier reacendeu tensões antigas entre ciência da computação teórica e computação prática. Comentadores questionam o uso de modelos idealizados, como aritmética complexa exata e operações de custo unitário, argumentando que eles permitem melhorias assintóticas “galácticas” que são impossíveis de realizar em hardware físico. Outros defendem a teoria pura e a análise big-O como historicamente importantes e potencialmente relevantes no futuro, ao mesmo tempo alertando que provas geradas por IA podem amplificar fraquezas existentes na forma como resultados de complexidade são especificados e interpretados.
Natureza dos supostos resultados mais rápidos de FFT / multiplicação
- Muitos veem os resultados da OpenAI sobre FFT e multiplicação de inteiros como usando um modelo muito forte, arguivelmente irrealista: aritmética complexa exata ou aritmética de custo unitário sobre números cujo módulo cresce superpolinomialmente no tamanho da entrada.
- Críticos argumentam que a aceleração assintótica “vem” de esconder trabalho em operações tratadas como O(1) (por exemplo, multiplicação de números enormes), então a melhoria pode ser mais sobre o modelo do que sobre a computação em si.
- Outros observam que variantes em corpos finitos (usados em criptografia) podem se ajustar melhor a modelos de custo realistas e, assim, ser mais significativas.
Big-O, constantes e algoritmos “galácticos”
- Tema recorrente: big-O ignora constantes, então algoritmos “galácticos” podem vencer n log n assintoticamente, mas apenas para n absurdamente grandes.
- Alguns dizem que isso torna tais resultados praticamente inúteis ou até “explorações” do formalismo; outros contrapõem que big-O e classes de complexidade continuam sendo ferramentas teóricas muito úteis.
- O teorema de speedup de Blum é invocado: limites de tempo sempre podem ser melhorados ao custo de espaço, então “quebrar” uma barreira n log n não é necessariamente um limite físico profundo.
Modelos de computação
- Debate sobre modelos: máquinas de Turing vs modelos registro/RAM vs Real RAM vs aritmética exata complexa/racional.
- Defensores: qualquer modelo é uma abstração; já idealizamos operações com inteiros como custo constante.
- Críticos: alguns modelos (por exemplo, aritmética complexa exata com magnitude ilimitada) são “mais errados” que outros se o objetivo é aproximar computadores reais ou a física.
Valor e propósito da ciência da computação teórica
- Um lado: se teóricos não se importam com desempenho prático, seu trabalho é um jogo de quebra-cabeça de pouco interesse externo; resultados galácticos e modelos irrealistas reforçam essa percepção.
- Lado oposto: a teoria frequentemente precede aplicações; muitas ideias historicamente “inúteis” (aritmética modular, teoria dos números, relatividade) tornaram-se cruciais depois. Não é possível prever de forma confiável qual matemática será importante.
- Alguns enfatizam que TCS é essencialmente matemática, não engenharia; reclamar que é impraticável revela um equívoco sobre seus objetivos.
Matemática gerada por IA e dinâmicas da comunidade
- Vários comentaristas sentem que a crítica é, na verdade, sobre ciência da computação teórica em geral, com OpenAI usada como gancho.
- Há preocupações de que LLMs vão produzir em massa resultados formalmente corretos, mas que exploram o modelo ou são galácticos, sobrecarregando revisores humanos e desalinhando incentivos.
- Outros acolhem a matemática em si e argumentam que, a menos que erros concretos ou afirmações incorretas sejam mostrados, descartar o trabalho como “slop” ou “slopository” é mais uma reclamação cultural do que uma crítica técnica.