Het artikel beschrijft de 'Mathocalypse': een gebeurtenis waarbij OpenAI 372 complexe wiskundige resultaten heeft vrijgegeven, waaronder het bewijs voor de Unique Games Conjecture (UGC). Hoewel de resultaten zijn geverifieerd via Lean-certificaten, zijn de bewijzen zo bizar en onintuïtief geschreven dat ze voor mensen vrijwel onleesbaar zijn zonder AI-ondersteuning.
Naast de UGC worden diverse andere doorbraken genoemd op het gebied van complexiteitstheorie, quantum-complexiteit en berekenbaarheid. De auteur maakt een onderscheid tussen het 'OpenAI-model' (een directe dump van onverteerbare data) en het 'Anthropic-model' (waarbij menselijke wiskundigen de kans kregen de resultaten eerst begrijpelijk te maken).
De auteur reflecteert filosofisch op de positie van de menselijke wiskundige: men is plotseling 'geteleporteerd naar de top van de berg' zonder de klim te hebben ervaren. Ondanks de schok is er optimisme dat AI als gids kan dienen, mits de gemeenschap het heroïsche avontuur van het ontdekken niet verliest. Tot slot wordt opgemerkt dat cryptografie opvallend ontbreekt in de lijst, wat kan duiden op strategische geheimhouding door AI-labs.
De Mathocalypse
Gisteravond tartte mijn 9-jarige zoon mijn vrouw, complexiteitstheoreticus Dana Moshkovitz, als volgt: "Mama, ik hoorde dat je bent verslagen! Ik hoorde dat een robot het wiskundige probleem heeft opgelost waar je je hele carrière aan hebt gewerkt! OEF!"
Hoewel mijn zoon zich als een brınıza gedroeg, had hij niet ongelijk. Of je er nu enthousiast, gedeprimeerd, boos of iets anders over bent: gisteren was ongetwijfeld een van de grootste dagen in de wiskundige geschiedenis. En ja, onder de 372 enorme resultaten die gisteren door OpenAI werden vrijgegeven — op aanbeveling van de adviesgroep bestaande uit Timothy Gowers, Edward Witten en andere vooraanstaande wiskundigen — zat een bewijs van de Unique Games Conjecture (UGC) van Subhash Khot. Dit is een stelling waar mijn vrouw aan heeft gewerkt om deze te bewijzen, zolang als ik haar ken. (De UGC impliceert dat een hele reeks optimalisatieproblemen echt NP-hard zijn, zelfs als je slechts een benadering wilt die iets beter is dan wat je krijgt via semidefinite programming relaxation, een van onze belangrijkste instrumenten.)
Of althans, we zijn er vrij zeker van dat het een bewijs is! Er is een Lean-certificaat, net als bij sommige van de andere 372 baanbrekende resultaten (maar niet bij alle). Het lijkt er echter op dat nog geen enkel mens een van deze bewijzen echt heeft begrepen; de race om dat wel te doen is net begonnen. Als je een idee wilt van hoe die race eruitziet, volgt hier een deel van wat Dana me gisteravond appte:
Het voelt alsof het is geschreven door iemand die op psychedelica is. Zo veel is onduidelijk en slaat nergens op. Er wordt veel naamgedropt van eerder werk zonder te bespreken waarom dit kan worden gebruikt ondanks onmogelijkheidsresultaten.
In feite is het paper zo verschrikkelijk geschreven dat het onmogelijk is om het te lezen zonder hulp van AI.
Ik vroeg Astra om redelijke claims over volledigheid en correctheid van de noise gadget en die gaf ze door claims uit het hele paper te combineren.
Ze hebben ook directe optimale NP-hardheidsbewijzen voor de belangrijkste toepassingen van de UGC (Max Cut en alle CSP) die de UGC omzeilen.
Het UGC-bewijs introduceert een volledig nieuwe, bizarre code met een noise test. Het is een soort krankzinnige recursieve constructie.
Het is niet de long code, niet de short code – het is een soort buitenaardse waanzin.
Ik denk nog steeds dat er misschien een bewijs is dat de half space code gebruikt (die is natuurlijker).
De citaties zijn vaak irrelevant en verwarrend.
Een mogelijke toekomst is een wiskundige wereld die hemels is als je visie/creatieve ideeën hebt die AI kan helpen controleren en implementeren.
En natuurlijk is er veel voor ons te leren van de aliens.
Als je je afvraagt welke emoties Dana voelt — nou, waarschijnlijk alle! Zelfs terwijl een centraal loopdoel is gevallen door een robot, zijn er voor haar tenminste twee verzachtende factoren. Ten eerste kan ze zich gerechtvaardigd voelen dat de UGC uiteindelijk waar was, iets waarvan ze nooit heeft getwijfeld, zelfs toen veel van haar collega's dat wel deden! Ten tweede zitten we nu in de wiskunde, theoretische informatica en mathematische fysica — althans zij die erom gaven om het oplossen van scherp geformuleerde problemen — allemaal in hetzelfde schuitje.
Een selectie van de resultaten
Naast de Unique Games Conjecture is hier een kleine steekproef van de schatten uit de grot van Aladdin waar ik de komende weken waarschijnlijk de meeste aandacht aan zal besteden:
- L = BPL: (d.w.z. probabilistische logspace en deterministische logspace zijn hetzelfde), een van de grote derandomisatie-conjecturen net onder P = BPP. Hoewel de waarheid hiervan nooit serieus in twijfel is getrokken, was er een hele subgemeenschap die zich richtte op het bewijzen hiervan.
- Fourier-transformatie en integer-vermenigvuldiging in minder dan $O(n \log n)$ tijd: Hiermee wordt een barrière doorbroken die sinds de jaren 60 bestond. De nieuwe rekentijd is, voor wie dat nieuwsgierig is, $O(n \log^{0.9999999999999} n)$, min of meer.
- Positieve oplossing voor het Unitary Synthesis Problem: Een probleem dat Greg Kuperberg en ik in 2007 hebben geformuleerd. Voor elke $n$-qubit unitteste transformatie $U$ bestaat er een klassiek orakel $A$ zodanig dat $U$ in quantum-polynomiale tijd kan worden geïmplementeerd met toegang tot $A$. Dit is het tegenovergestelde van wat de meesten van ons verwachtten, en zou implicaties kunnen hebben voor bijvoorbeeld het computationele probleem van het decoderen van Hawkingstraling van een zwart gat en vele andere problemen in de quantum-complexiteitstheorie — mits we een efficiënte manier hadden om het orakel $A$ te construeren, wat dit paper niet geeft.
- Parity zit niet in $\text{QAC}^0$: Een van de grote vragen in de quantum-complexiteitstheorie sinds 1999 waar veel van mijn collega's dichtbij waren.
- Bijna 4de-macht scheiding tussen gerandomiseerde en quantum query-complexiteit voor totale Booleaanse functies: Een favoriet probleem van mij sinds 1998, toen we alleen wisten dat de optimale scheidende exponent tussen 2 en 6 lag. De afgelopen jaren wisten we dat het tussen 3 en 4 lag. Dit sluit dat verhaal eindelijk af.
- Een superkwadratische scheiding tussen sensitiviteit en blok-sensitiviteit.
- Area law voor 2D gapped Hamiltonians: Een van de belangrijkste open problemen in de Hamiltonian-complexiteit.
- Matrixvermenigvuldiging in $O(n^{9/4})$ tijd: Voor een keer een rationele exponent, en via een volledig andere benadering dan die gebruikt werd voor $O(n^{2.373})$ en dergelijke.
- $\Omega(n^3)$ ondergrens voor de determinantale complexiteit van de permanent: Een verbetering van de vorige beste grens die kwadratisch was.
- Een gerandomiseerd poly-tijd algoritme om het aantal perfecte matchings in een algemene graaf benaderend te tellen, evenals een gerandomiseerd bijna lineair-tijd algoritme voor het vinden van een maximum matching in zo'n graaf.
- Onberekenbaarheid van het oplossen van polynomiale vergelijkingen over de rationele getallen: Dit was waarschijnlijk het grootste open probleem in de berekenbaarheidstheorie (let op dat de onberekenbaarheid van het oplossen van diofantische vergelijkingen, d.w.z. polynomiale vergelijkingen over de gehele getallen, in de jaren 70 werd bewezen, wat een negatief antwoord gaf op Hilberts 10de probleem).
Elk van de bovenstaande resultaten had op zichzelf gemakkelijk het "resultaat van het jaar" kunnen zijn in een bepaald vakgebied (en in sommige gevallen, zoals Unique Games en L=BPL, in de gehele theoretische informatica). En er is veel dat ik heb weggelaten. Er zijn even verbazingwekkende wonderen in de getaltheorie, combinatoriek, algebraïsche meetkunde, analyse en vrijwel elk ander gebied van de wiskunde, waarvan ik de meeste nooit zal begrijpen, hoewel ik zal opmerken dat het voortgang bevat richting de Riemann-hypothese, de Hodge-conjectuur en de Birch-Swinnerton-Dyer-conjectuur (d.w.z. de meerderheid van de resterende Millennium-problemen).
We kunnen troost putten uit wat ontbreekt op de lijst. P $\neq$ NP staat er niet bij, noch P = BPP of NEXP $\not\subset$ P/poly, en zeker niet wegens een gebrek aan pogingen. Blijkbaar zijn de grootste open problemen van de theoretische informatica inderdaad erg moeilijk!
Alternatieve doorbraken en communicatiemodellen
Eén dag vóór de OpenAI-dump, dus maandagavond, plaatsten Virginia Williams en Josh Alman een arXiv-preprint die het 3SUM-probleem oplost in $O(n^{1.9992})$ tijd, en het All-Pairs Shortest Paths-probleem in $O(n^{2.9995})$ tijd. Hiermee worden halveeeeuwen oude conjuncturen weerlegd die stelden dat de juiste antwoorden respectievelijk $n^2-o(1)$ en $n^3-o(1)$ waren. In dit geval was het niet een OpenAI-model dat het cruciale idee leverde, maar een model van Anthropic!
Anthropic koos echter voor een andere aanpak dan OpenAI: in plaats van de onverteerbare oplossingen aan de wereld te presenteren, gaven ze Virginia en Josh de kans om een verteerbare versie te schrijven en aan te kondigen in ruil voor compensatie.
Hier zijn de twee belangrijkste modellen voor het communiceren van AI-wiskunde-doorbraken ontstaan, en ze hebben beide sterke en zwakke punten. Het "OpenAI-model" creëert een krankzinnige race onder mensen om een rommelig AI-bewijs te verteren en uit te leggen (werk dat gemakkelijk een combinatie kan zijn van ondankbaar, nauwelijks erkend, competitief en niet leuk), terwijl het "Anthropic-model" een privaat bedrijf in de positie plaatst om te kiezen welke menselijke wiskundigen de gezanten van de AI mogen zijn.
De techniek achter de "Mathocalypse"
Voor wie zich afvraagt: blijkbaar was het AI-model dat al deze wonderen produceerde geen op maat gemaakt apparaat van 10.000 agenten die miljoenen dollars aan compute verbruikten, zoals werd gebruikt voor het construeren van een finite-time blowup voor de Navier-Stokes-vergelijkingen. In plaats daarvan was het simpelweg het nieuwste interne OpenAI-model — een model dat mogelijk binnen enkele maanden aan betalende ChatGPT-klanten wordt uitgebracht, afhankelijk van de aanbevelingen van de veiligheidsraad van OpenAI. (Mijn 9-jarige zoon: "Oh, die zouden ze absoluut niet moeten uitbrengen. Als het al die wiskundige problemen kan oplossen, kan het onmogelijk veilig zijn.") Blijkbaar gebruikten ze gemiddeld ongeveer 3 uur aan GPT-Pro-niveau compute per opgelost probleem.
Ook is het vermeldenswaardig dat ze het model hebben getest op ongeveer 8.000 problemen. Dus op dit moment lost het "slechts" ongeveer 5% van de langlopende open wiskundige problemen op waar het om gevraagd wordt — problemen waar hele gemeenschappen jaren aan hebben gewerkt — na één poging van 3 uur.
Reflecties over de toekomst
Ik ben blij te zien dat de gemeenschap van theoretische informatica zich schrapst. Bij het Simons Institute in Berkeley, hier bij UT Austin en elders hoor ik verhalen over onderzoekers die zich haasten om de manuscripten door te spitten en ze te begrijpen en uit te leggen — want wat doen we anders? Hoe kunnen we anders het ambacht voortzetten waaraan we een groot deel van ons leven hebben gewijd?
Als je een idee wilt van hoe de zaken er nu voorstaan in de wiskunde, stel je dan een jager-verzamelaar voor die zijn hele leven heeft geleerd te overleven diep in een onvergeeflijk regenwoud. Dan verschijnt er plotseling een gigantisch resort-hotel vlak naast hem, met een helipad, verwarmde zwembaden en Airbnb's. Zonder een seconde te aarzelen zegt de jager-verzamelaar: "Vooruit, prima, mijn nieuwe baan is dus om wildernis-retraites voor de toeristen te organiseren, of zoiets."
In Quanta magazine probeerde Jordana Cepelewitz een andere metafoor:
Het is alsof je geteleporteerd bent naar de top van een hoge berg. Omringd door mist heb je geen idee waar je bent of wat er om je heen is. Je weet niet hoe jouw berg verbonden is met anderen, en je hebt geen uitrusting om je te helpen verkennen, geen manier om iemand anders bij je te laten aansluiten. Als je de berg zelf had beklommen, had je ervaren hoe het menselijk lichaam zich aanpast aan de hoogte en veranderingen in zuurstofgehaltes. Je had tools moeten uitvinden om te navigeren, om steile kliffen te beklimmen, of om een schuilplaats te maken. Je had een mede-ontdekker kunnen ontmoeten, samen kunnen verdwalen in een verborgen vallei, en een plant hebben gevonden die in een levensreddend medicijn kon worden veranderd.
In plaats daarvan zit je op de piek maar in het donker, terwijl de maker van de teleportatiemachine je vertelt dat hij de wildernis beter kan verkennen dan ieder mens.
Voor elk van deze bergen voel ik me optimistisch dat we kunnen doen wat we altijd hebben gedaan: de mist klaren en het pad vinden, maar nu met de teleportatiemachine als gids. De grotere uitdaging zal zijn om een gemeenschap te koesteren die nog steeds geeft om het heroïsche avontuur van het vinden van de paden naar deze bergen in een wereld met de machine.
Omgang met scepsis
De ervaring leert dat er, zelfs nu, mensen zullen zijn die in een neerbuigende toon uitleggen waarom niets hiervan echt is en waarom het niet telt. Als zodanige mensen in staat zouden zijn om onder de indruk te raken van iets dat in de empirische wereld gebeurt, of om hun mening bij te stellen, dan zouden ze dat al jaren geleden hebben gedaan, lang voordat we het punt van een feitelijke Mathocalypse bereikten.
Ze zullen zeggen dat de vermeende oplossingen helemaal geen oplossingen zijn, maar gewoon "AI-slop". Of misschien waren geen van de 372 opgeloste open problemen echte wiskundige problemen, maar slechts verheerlijkte wedstrijd-puzzels en trivialiteiten. (Immers, er is nog steeds geen Riemann-hypothese!) Of misschien moet de hele 4000 jaar oude discipline van de wiskunde worden overboord gegooid: het blijkt dat het allemaal gewoon puzzelen en trivialiteiten waren; het enige verschil is dat de trivialiteit nu gemaskeerd is. In ieder geval is het belangrijkste dat het ware innerlijke sanctum van menselijke creativiteit niet is doorbroken en waarschijnlijk nooit zal worden, en ook dat Sam Altman en Dario Amodei verachtelijke kleine nerds zijn.
Persoonlijke noot
Gisteravond, terwijl ik me eigenlijk had moeten verdiepen in sommige van de honderden papers van OpenAI en/of deze post had moeten schrijven, besloot ik tijd door te brengen met mijn kinderen. Ze wilden een filmavond, dus ik stelde iets voor wat ze nog nooit hadden gezien (en wat ik in decennia niet had gezien), en dat bol stond van het nuchtere, praktische advies voor de wereld waarin zij zullen opgroeien: Terminator 2.
***
Update: Zoals verschillende mensen hebben opgemerkt, is cryptografie een subveld dat opvallend afwezig is op de lijst van 376 papers van OpenAI! Mijn bronnen vertellen me echter dat de AI-bedrijven nu voorzichtig en discreet zijn begonnen met het onderzoeken of hun nieuwste interne modellen belangrijke cryptografische protocollen en primitieven kunnen breken. Als dat het geval is, zou het zeker fijn zijn om hierop vooruit te lopen voordat de rest van de wereld hetzelfde ontdekt.
Nog een update: De verklaring van de Advisory Group on Mathematics and Artificial Intelligence (AGMAI) is zeer zorgvuldig geformuleerd en is het lezen waard:
Zoals een paar weken geleden is aangekondigd, heeft OpenAI een grote collectie wiskundige resultaten vrijgegeven die zijn gegenereerd door een intern model, met oplossingen voor honderden open vragen. Dit is een belangrijke gebeurtenis voor de wiskunde, met consequenties voor zowel de wiskunde als de wiskundige gemeenschap die veel verder gaan dan de individuele resultaten.
De adviserende rol van AGMAI moet niet worden geïnterpreteerd als een oordeel over de impact van deze resultaten of als een goedkeuring van het proces waarmee OpenAI ze heeft verkregen. Wij spreken niet namens de gehele wiskundige gemeenschap, en alleen de wiskundige gemeenschap kan de nodige beoordeling uitvoeren.
Het openbaar maken van dit werk is een eerste stap. Deze release is het begin, niet de voltooiing, van het proces van menselijk begrip en de integratie van het werk in de wiskundige kennis. Tegelijkertijd kan de toekomst van wiskundig onderzoek niet alleen bestaan uit het begrijpen van resultaten die zijn geproduceerd door AI-labs. Wiskundigen moeten in staat zijn hun eigen vragen te formuleren, hun eigen benaderingen te ontwikkelen en richtingen te verkennen die niet zijn geselecteerd als voorbeelden van de capaciteiten van een AI-systeem. Gelijkheid in toegang tot krachtige onderzoekstools en adequate computationele middelen zijn essentieel voor die vrijheid.
Wij bevestigen onze gepubliceerde aanbevelingen over verantwoord vrijgeven. We hebben deze besproken met OpenAI en waarderen de bereidheid van het bedrijf om hieraan mee te werken. Hoewel we deze discussies constructief vinden, is het uiteindelijk aan de wiskundige gemeenschap om te beoordelen in hoeverre onze aanbevelingen succesvol zijn gevolgd, en of er andere zijn die we zouden moeten suggereren. We blijven toegewijd aan het betrekken van elk frontier AI-lab bij deze vragen en hebben er al verschillende mee contact gehad.
De Mathocalypse
Gisteravond tartte mijn 9-jarige zoon mijn vrouw, complexiteitstheoreticus Dana Moshkovitz, als volgt: "Mama, ik hoorde dat je bent verslagen! Ik hoorde dat een robot het wiskundige probleem heeft opgelost waar je je hele carrière aan hebt gewerkt! OEF!"
Hoewel mijn zoon zich als een brınıza gedroeg, had hij niet ongelijk. Of je er nu enthousiast, gedeprimeerd, boos of iets anders over bent: gisteren was ongetwijfeld een van de grootste dagen in de wiskundige geschiedenis. En ja, onder de 372 enorme resultaten die gisteren door OpenAI werden vrijgegeven — op aanbeveling van de adviesgroep bestaande uit Timothy Gowers, Edward Witten en andere vooraanstaande wiskundigen — zat een bewijs van de Unique Games Conjecture (UGC) van Subhash Khot. Dit is een stelling waar mijn vrouw aan heeft gewerkt om deze te bewijzen, zolang als ik haar ken. (De UGC impliceert dat een hele reeks optimalisatieproblemen echt NP-hard zijn, zelfs als je slechts een benadering wilt die iets beter is dan wat je krijgt via semidefinite programming relaxation, een van onze belangrijkste instrumenten.)
Of althans, we zijn er vrij zeker van dat het een bewijs is! Er is een Lean-certificaat, net als bij sommige van de andere 372 baanbrekende resultaten (maar niet bij alle). Het lijkt er echter op dat nog geen enkel mens een van deze bewijzen echt heeft begrepen; de race om dat wel te doen is net begonnen. Als je een idee wilt van hoe die race eruitziet, volgt hier een deel van wat Dana me gisteravond appte:
Het voelt alsof het is geschreven door iemand die op psychedelica is. Zo veel is onduidelijk en slaat nergens op. Er wordt veel naamgedropt van eerder werk zonder te bespreken waarom dit kan worden gebruikt ondanks onmogelijkheidsresultaten.
In feite is het paper zo verschrikkelijk geschreven dat het onmogelijk is om het te lezen zonder hulp van AI.
Ik vroeg Astra om redelijke claims over volledigheid en correctheid van de noise gadget en die gaf ze door claims uit het hele paper te combineren.
Ze hebben ook directe optimale NP-hardheidsbewijzen voor de belangrijkste toepassingen van de UGC (Max Cut en alle CSP) die de UGC omzeilen.
Het UGC-bewijs introduceert een volledig nieuwe, bizarre code met een noise test. Het is een soort krankzinnige recursieve constructie.
Het is niet de long code, niet de short code – het is een soort buitenaardse waanzin.
Ik denk nog steeds dat er misschien een bewijs is dat de half space code gebruikt (die is natuurlijker).
De citaties zijn vaak irrelevant en verwarrend.
Een mogelijke toekomst is een wiskundige wereld die hemels is als je visie/creatieve ideeën hebt die AI kan helpen controleren en implementeren.
En natuurlijk is er veel voor ons te leren van de aliens.
Als je je afvraagt welke emoties Dana voelt — nou, waarschijnlijk alle! Zelfs terwijl een centraal loopdoel is gevallen door een robot, zijn er voor haar tenminste twee verzachtende factoren. Ten eerste kan ze zich gerechtvaardigd voelen dat de UGC uiteindelijk waar was, iets waarvan ze nooit heeft getwijfeld, zelfs toen veel van haar collega's dat wel deden! Ten tweede zitten we nu in de wiskunde, theoretische informatica en mathematische fysica — althans zij die erom gaven om het oplossen van scherp geformuleerde problemen — allemaal in hetzelfde schuitje.
Een selectie van de resultaten
Naast de Unique Games Conjecture is hier een kleine steekproef van de schatten uit de grot van Aladdin waar ik de komende weken waarschijnlijk de meeste aandacht aan zal besteden:
- L = BPL: (d.w.z. probabilistische logspace en deterministische logspace zijn hetzelfde), een van de grote derandomisatie-conjecturen net onder P = BPP. Hoewel de waarheid hiervan nooit serieus in twijfel is getrokken, was er een hele subgemeenschap die zich richtte op het bewijzen hiervan.
- Fourier-transformatie en integer-vermenigvuldiging in minder dan $O(n \log n)$ tijd: Hiermee wordt een barrière doorbroken die sinds de jaren 60 bestond. De nieuwe rekentijd is, voor wie dat nieuwsgierig is, $O(n \log^{0.9999999999999} n)$, min of meer.
- Positieve oplossing voor het Unitary Synthesis Problem: Een probleem dat Greg Kuperberg en ik in 2007 hebben geformuleerd. Voor elke $n$-qubit unitteste transformatie $U$ bestaat er een klassiek orakel $A$ zodanig dat $U$ in quantum-polynomiale tijd kan worden geïmplementeerd met toegang tot $A$. Dit is het tegenovergestelde van wat de meesten van ons verwachtten, en zou implicaties kunnen hebben voor bijvoorbeeld het computationele probleem van het decoderen van Hawkingstraling van een zwart gat en vele andere problemen in de quantum-complexiteitstheorie — mits we een efficiënte manier hadden om het orakel $A$ te construeren, wat dit paper niet geeft.
- Parity zit niet in $\text{QAC}^0$: Een van de grote vragen in de quantum-complexiteitstheorie sinds 1999 waar veel van mijn collega's dichtbij waren.
- Bijna 4de-macht scheiding tussen gerandomiseerde en quantum query-complexiteit voor totale Booleaanse functies: Een favoriet probleem van mij sinds 1998, toen we alleen wisten dat de optimale scheidende exponent tussen 2 en 6 lag. De afgelopen jaren wisten we dat het tussen 3 en 4 lag. Dit sluit dat verhaal eindelijk af.
- Een superkwadratische scheiding tussen sensitiviteit en blok-sensitiviteit.
- Area law voor 2D gapped Hamiltonians: Een van de belangrijkste open problemen in de Hamiltonian-complexiteit.
- Matrixvermenigvuldiging in $O(n^{9/4})$ tijd: Voor een keer een rationele exponent, en via een volledig andere benadering dan die gebruikt werd voor $O(n^{2.373})$ en dergelijke.
- $\Omega(n^3)$ ondergrens voor de determinantale complexiteit van de permanent: Een verbetering van de vorige beste grens die kwadratisch was.
- Een gerandomiseerd poly-tijd algoritme om het aantal perfecte matchings in een algemene graaf benaderend te tellen, evenals een gerandomiseerd bijna lineair-tijd algoritme voor het vinden van een maximum matching in zo'n graaf.
- Onberekenbaarheid van het oplossen van polynomiale vergelijkingen over de rationele getallen: Dit was waarschijnlijk het grootste open probleem in de berekenbaarheidstheorie (let op dat de onberekenbaarheid van het oplossen van diofantische vergelijkingen, d.w.z. polynomiale vergelijkingen over de gehele getallen, in de jaren 70 werd bewezen, wat een negatief antwoord gaf op Hilberts 10de probleem).
Elk van de bovenstaande resultaten had op zichzelf gemakkelijk het "resultaat van het jaar" kunnen zijn in een bepaald vakgebied (en in sommige gevallen, zoals Unique Games en L=BPL, in de gehele theoretische informatica). En er is veel dat ik heb weggelaten. Er zijn even verbazingwekkende wonderen in de getaltheorie, combinatoriek, algebraïsche meetkunde, analyse en vrijwel elk ander gebied van de wiskunde, waarvan ik de meeste nooit zal begrijpen, hoewel ik zal opmerken dat het voortgang bevat richting de Riemann-hypothese, de Hodge-conjectuur en de Birch-Swinnerton-Dyer-conjectuur (d.w.z. de meerderheid van de resterende Millennium-problemen).
We kunnen troost putten uit wat ontbreekt op de lijst. P $\neq$ NP staat er niet bij, noch P = BPP of NEXP $\not\subset$ P/poly, en zeker niet wegens een gebrek aan pogingen. Blijkbaar zijn de grootste open problemen van de theoretische informatica inderdaad erg moeilijk!
Alternatieve doorbraken en communicatiemodellen
Eén dag vóór de OpenAI-dump, dus maandagavond, plaatsten Virginia Williams en Josh Alman een arXiv-preprint die het 3SUM-probleem oplost in $O(n^{1.9992})$ tijd, en het All-Pairs Shortest Paths-probleem in $O(n^{2.9995})$ tijd. Hiermee worden halveeeeuwen oude conjuncturen weerlegd die stelden dat de juiste antwoorden respectievelijk $n^2-o(1)$ en $n^3-o(1)$ waren. In dit geval was het niet een OpenAI-model dat het cruciale idee leverde, maar een model van Anthropic!
Anthropic koos echter voor een andere aanpak dan OpenAI: in plaats van de onverteerbare oplossingen aan de wereld te presenteren, gaven ze Virginia en Josh de kans om een verteerbare versie te schrijven en aan te kondigen in ruil voor compensatie.
Hier zijn de twee belangrijkste modellen voor het communiceren van AI-wiskunde-doorbraken ontstaan, en ze hebben beide sterke en zwakke punten. Het "OpenAI-model" creëert een krankzinnige race onder mensen om een rommelig AI-bewijs te verteren en uit te leggen (werk dat gemakkelijk een combinatie kan zijn van ondankbaar, nauwelijks erkend, competitief en niet leuk), terwijl het "Anthropic-model" een privaat bedrijf in de positie plaatst om te kiezen welke menselijke wiskundigen de gezanten van de AI mogen zijn.
De techniek achter de "Mathocalypse"
Voor wie zich afvraagt: blijkbaar was het AI-model dat al deze wonderen produceerde geen op maat gemaakt apparaat van 10.000 agenten die miljoenen dollars aan compute verbruikten, zoals werd gebruikt voor het construeren van een finite-time blowup voor de Navier-Stokes-vergelijkingen. In plaats daarvan was het simpelweg het nieuwste interne OpenAI-model — een model dat mogelijk binnen enkele maanden aan betalende ChatGPT-klanten wordt uitgebracht, afhankelijk van de aanbevelingen van de veiligheidsraad van OpenAI. (Mijn 9-jarige zoon: "Oh, die zouden ze absoluut niet moeten uitbrengen. Als het al die wiskundige problemen kan oplossen, kan het onmogelijk veilig zijn.") Blijkbaar gebruikten ze gemiddeld ongeveer 3 uur aan GPT-Pro-niveau compute per opgelost probleem.
Ook is het vermeldenswaardig dat ze het model hebben getest op ongeveer 8.000 problemen. Dus op dit moment lost het "slechts" ongeveer 5% van de langlopende open wiskundige problemen op waar het om gevraagd wordt — problemen waar hele gemeenschappen jaren aan hebben gewerkt — na één poging van 3 uur.
Reflecties over de toekomst
Ik ben blij te zien dat de gemeenschap van theoretische informatica zich schrapst. Bij het Simons Institute in Berkeley, hier bij UT Austin en elders hoor ik verhalen over onderzoekers die zich haasten om de manuscripten door te spitten en ze te begrijpen en uit te leggen — want wat doen we anders? Hoe kunnen we anders het ambacht voortzetten waaraan we een groot deel van ons leven hebben gewijd?
Als je een idee wilt van hoe de zaken er nu voorstaan in de wiskunde, stel je dan een jager-verzamelaar voor die zijn hele leven heeft geleerd te overleven diep in een onvergeeflijk regenwoud. Dan verschijnt er plotseling een gigantisch resort-hotel vlak naast hem, met een helipad, verwarmde zwembaden en Airbnb's. Zonder een seconde te aarzelen zegt de jager-verzamelaar: "Vooruit, prima, mijn nieuwe baan is dus om wildernis-retraites voor de toeristen te organiseren, of zoiets."
In Quanta magazine probeerde Jordana Cepelewitz een andere metafoor:
Het is alsof je geteleporteerd bent naar de top van een hoge berg. Omringd door mist heb je geen idee waar je bent of wat er om je heen is. Je weet niet hoe jouw berg verbonden is met anderen, en je hebt geen uitrusting om je te helpen verkennen, geen manier om iemand anders bij je te laten aansluiten. Als je de berg zelf had beklommen, had je ervaren hoe het menselijk lichaam zich aanpast aan de hoogte en veranderingen in zuurstofgehaltes. Je had tools moeten uitvinden om te navigeren, om steile kliffen te beklimmen, of om een schuilplaats te maken. Je had een mede-ontdekker kunnen ontmoeten, samen kunnen verdwalen in een verborgen vallei, en een plant hebben gevonden die in een levensreddend medicijn kon worden veranderd.
In plaats daarvan zit je op de piek maar in het donker, terwijl de maker van de teleportatiemachine je vertelt dat hij de wildernis beter kan verkennen dan ieder mens.
Voor elk van deze bergen voel ik me optimistisch dat we kunnen doen wat we altijd hebben gedaan: de mist klaren en het pad vinden, maar nu met de teleportatiemachine als gids. De grotere uitdaging zal zijn om een gemeenschap te koesteren die nog steeds geeft om het heroïsche avontuur van het vinden van de paden naar deze bergen in een wereld met de machine.
Omgang met scepsis
De ervaring leert dat er, zelfs nu, mensen zullen zijn die in een neerbuigende toon uitleggen waarom niets hiervan echt is en waarom het niet telt. Als zodanige mensen in staat zouden zijn om onder de indruk te raken van iets dat in de empirische wereld gebeurt, of om hun mening bij te stellen, dan zouden ze dat al jaren geleden hebben gedaan, lang voordat we het punt van een feitelijke Mathocalypse bereikten.
Ze zullen zeggen dat de vermeende oplossingen helemaal geen oplossingen zijn, maar gewoon "AI-slop". Of misschien waren geen van de 372 opgeloste open problemen echte wiskundige problemen, maar slechts verheerlijkte wedstrijd-puzzels en trivialiteiten. (Immers, er is nog steeds geen Riemann-hypothese!) Of misschien moet de hele 4000 jaar oude discipline van de wiskunde worden overboord gegooid: het blijkt dat het allemaal gewoon puzzelen en trivialiteiten waren; het enige verschil is dat de trivialiteit nu gemaskeerd is. In ieder geval is het belangrijkste dat het ware innerlijke sanctum van menselijke creativiteit niet is doorbroken en waarschijnlijk nooit zal worden, en ook dat Sam Altman en Dario Amodei verachtelijke kleine nerds zijn.
Persoonlijke noot
Gisteravond, terwijl ik me eigenlijk had moeten verdiepen in sommige van de honderden papers van OpenAI en/of deze post had moeten schrijven, besloot ik tijd door te brengen met mijn kinderen. Ze wilden een filmavond, dus ik stelde iets voor wat ze nog nooit hadden gezien (en wat ik in decennia niet had gezien), en dat bol stond van het nuchtere, praktische advies voor de wereld waarin zij zullen opgroeien: Terminator 2.
***
Update: Zoals verschillende mensen hebben opgemerkt, is cryptografie een subveld dat opvallend afwezig is op de lijst van 376 papers van OpenAI! Mijn bronnen vertellen me echter dat de AI-bedrijven nu voorzichtig en discreet zijn begonnen met het onderzoeken of hun nieuwste interne modellen belangrijke cryptografische protocollen en primitieven kunnen breken. Als dat het geval is, zou het zeker fijn zijn om hierop vooruit te lopen voordat de rest van de wereld hetzelfde ontdekt.
Nog een update: De verklaring van de Advisory Group on Mathematics and Artificial Intelligence (AGMAI) is zeer zorgvuldig geformuleerd en is het lezen waard:
Zoals een paar weken geleden is aangekondigd, heeft OpenAI een grote collectie wiskundige resultaten vrijgegeven die zijn gegenereerd door een intern model, met oplossingen voor honderden open vragen. Dit is een belangrijke gebeurtenis voor de wiskunde, met consequenties voor zowel de wiskunde als de wiskundige gemeenschap die veel verder gaan dan de individuele resultaten.
De adviserende rol van AGMAI moet niet worden geïnterpreteerd als een oordeel over de impact van deze resultaten of als een goedkeuring van het proces waarmee OpenAI ze heeft verkregen. Wij spreken niet namens de gehele wiskundige gemeenschap, en alleen de wiskundige gemeenschap kan de nodige beoordeling uitvoeren.
Het openbaar maken van dit werk is een eerste stap. Deze release is het begin, niet de voltooiing, van het proces van menselijk begrip en de integratie van het werk in de wiskundige kennis. Tegelijkertijd kan de toekomst van wiskundig onderzoek niet alleen bestaan uit het begrijpen van resultaten die zijn geproduceerd door AI-labs. Wiskundigen moeten in staat zijn hun eigen vragen te formuleren, hun eigen benaderingen te ontwikkelen en richtingen te verkennen die niet zijn geselecteerd als voorbeelden van de capaciteiten van een AI-systeem. Gelijkheid in toegang tot krachtige onderzoekstools en adequate computationele middelen zijn essentieel voor die vrijheid.
Wij bevestigen onze gepubliceerde aanbevelingen over verantwoord vrijgeven. We hebben deze besproken met OpenAI en waarderen de bereidheid van het bedrijf om hieraan mee te werken. Hoewel we deze discussies constructief vinden, is het uiteindelijk aan de wiskundige gemeenschap om te beoordelen in hoeverre onze aanbevelingen succesvol zijn gevolgd, en of er andere zijn die we zouden moeten suggereren. We blijven toegewijd aan het betrekken van elk frontier AI-lab bij deze vragen en hebben er al verschillende mee contact gehad.
Groetjes,