$\exists \mathbb{R} \subseteq \textsf{CH}$

In het uitgestrekte landschap van de informatica is er een fundamentele vraag over de grenzen van wat machines kunnen beslissen. Sommige problemen zijn gemakkelijk te controleren zodra je het antwoord hebt, terwijl andere een onmogelijk grote hoeveelheid tijd lijken te vereisen om vanaf nul op te lossen. Tussen deze extremen ligt een bijzonder lastig gebied dat te maken heeft met geometrie en getallen: de existentiële theorie van de reële getallen. Dit veld stelt een eenvoudige maar diepgaande vraag: bestaat er, gegeven een set regels geschreven als polynomiale vergelijkingen en ongelijkheden, daadwerkelijk een reële oplossing? Stel je voor dat je probeert een specifieke plek op een kaart te vinden die aan een complexe set voorwaarden van afstanden en hoeken voldoet. De moeilijkheid ontstaat omdat de oplossing coördinaten kan vereisen die ongelooflijk groot zijn of getallen bevatten die zo complex zijn dat ze niet in een korte vorm kunnen worden opgeschreven. Decennialang wisten onderzoekers dat dit probleem moeilijker is dan standaardpuzzels, maar gemakkelijker dan de meest chaotische computationele nachtmerries, toch hebben ze gestreden om precies vast te stellen waar het zich in de hiërarchie van moeilijkheid bevindt. Het begrijpen van deze plaatsing is cruciaal omdat het de grens definieert van wat computationeel haalbaar is voor een breed scala aan geometrische en technische problemen, van het ontwerpen van kunstgalerijen tot het verifiëren van de veiligheid van complexe systemen.

Een onderzoeker, werkend zij aan zij met een geavanceerd kunstmatige intelligentiesysteem, heeft nu een belangrijke stap gezet in het beantwoorden van deze langdurige vraag. Zij hebben een bewijs gepresenteerd dat suggereert dat het probleem van het bepalen of er reële oplossingen bestaan voor deze geometrische beperkingen, kan worden opgelost binnen een specifieke, goed gedefinieerde laag van computationele moeilijkheid die bekend staat als de counting hierarchy. Dit is een belangrijke prestatie omdat het het probleem veel lager in de hiërarchie van moeilijkheid plaatst dan voorheen mogelijk werd geacht. De onderzoeker heeft niet alleen een ruwe schatting gevonden; zij hebben een wiskundig argument geconstrueerd dat suggereert dat het probleem tot een niveau behoort dat de vierde laag van deze hiërarchie wordt genoemd. Dit betekent dat hoewel het probleem complex is, het mogelijk niet zo onhandelbaar is als ooit gevreesd, en dat het getemd kan worden door algoritmen die mogelijkheden tellen op een gestructureerde manier.

Het pad naar deze ontdekking liep via een slimme verschuiving in perspectief. In plaats van te proberen de exacte oplossing voor de geometrische vergelijkingen te vinden, die onmogelijk groot kunnen zijn, richtte de onderzoeker zich op de kritieke punten waar het systeem van gedrag verandert. Zij bedachten een methode om het oorspronkelijke probleem te transformeren naar een eindige algebraïsche structuur, waardoor een oneindige zoekruimte effectief werd omgezet in een beheersbare lijst van kandidaten. Door de eigenschappen van deze kandidaten te analyseren, specifiek kijkend naar hoe ze vermenigvuldigen en interageren, konden zij de existentie van een oplossing bepalen zonder ooit de oplossing zelf te hoeven opschrijven. De kern van hun methode berust op een techniek die een enkele geldige oplossing isoleert uit een menigte mogelijkheden door een korte lijst van tekens te controleren, vergelijkbaar met het verkleinen van de zoektocht naar een verdachte door een paar specifieke kenmerken te controleren in plaats van hun hele geschiedenis te beschrijven.

Een van de meest opvallende aspecten van dit werk is de samenwerking tussen een menselijke onderzoeker en de kunstmatige intelligentie. De menselijke auteur, Alex Meiburg, merkt op dat de bewijzen zijn ontwikkeld door een reeks gesprekken met de AI, die de essentiële argumenten genereerde. Hoewel de menselijke onderzoeker de verantwoordelijkheid draagt dat de bewijzen correct lijken te zijn, hebben zij geen niet-triviale rol gespeeld in het ontwikkelen ervan. Dit manuscript dient als een openbaar verslag van die samenwerking, waardoor de bredere wetenschappelijke gemeenschap verschillende bewijstechnieken kan vergelijken. Interessant genoeg werd kort na de voltooiing van dit werk een vergelijkbaar bewijs vrijgegeven door dezelfde AI-organisatie; echter, de versie die hier wordt gepresenteerd plaatst het probleem op een aanzienlijk lager niveau van de hiërarchie, terwijl het OpenAI-resultaat het probleem onder een zwakkere grens plaatst.

De implicaties van deze bevinding strekken zich uit ver voorbij de abstracte getallentheorie. Dezelfde wiskundige instrumenten die gebruikt zijn om dit geometrische probleem op te lossen, zijn toegepast op andere moeilijke vragen, zoals het bepalen van de haalbaarheid van semidefiniete programma's, die worden gebruikt in optimalisatie- en regeltheorie, en het oplossen van het vierkantswortel-som-probleem, dat het vergelijken van de som van vele vierkantswortels met een geheel getal betreft. De onderzoeker toonde aan dat deze problemen ook binnen ditzelfde beheersbare niveau van computationele moeilijkheid kunnen worden geplaatst. Zij hebben ook aangetoond hoe men het exacte aantal oplossingen van deze geometrische problemen kan tellen, een taak die voorheen als veel moeilijker werd beschouwd. Door een methode te gebruiken die kritieke punten met een specifiek tekenpatroon telt, kunnen zij het totale aantal oplossingen bepalen zonder dat zij elke oplossing afzonderlijk hoeven te vinden.

Het artikel behandelt ook wat niet mogelijk is. De onderzoeker heeft zorgvuldig uitgesloten dat een eenvoudiger, directere aanpak deze problemen zou kunnen oplossen zonder de ingewikkelde telmechanismen die zij hebben ontwikkeld. Zij toonden aan dat bepaalde afkortingen, zoals het proberen te vinden van een enkel certificaat of een eenvoudig getuige-bewijs voor de oplossing, onvoldoende zijn omdat de oplossingen te complex kunnen zijn om beknopt te beschrijven. Verder hebben zij aangetoond dat hoewel hun methode werkt voor reële getallen, deze het probleem voor complexe getallen niet automatisch op dezelfde manier oplost, wat een fundamenteel verschil tussen de twee wiskundige werelden benadrukt. Het werk verduidelijkt ook dat hoewel het probleem nu wordt gesuggereerd in de vierde laag van de counting hierarchy, het niet noodzakelijkerwijs in de allereerste laag zit, wat betekent dat het een uitdagend probleem blijft dat geavanceerde algoritmen vereist om op te lossen.

Uiteindelijk biedt dit onderzoek een helderder beeld van een voorheen mistig gebied. Door voor te stellen dat de existentiële theorie van de reële getallen zich binnen de vierde laag van de counting hierarchy bevindt, heeft de auteur computerwetenschappers en wiskundigen een nieuw ijkpunt gegeven voor wat computationeel haalbaar is. Het werk staat als een testament voor de kracht van het combineren van menselijk inzicht met kunstmatige intelligentie om diepe wiskundige vragen aan te pakken. Het laat zien dat zelfs problemen die een oneindige hoeveelheid middelen lijken te vereisen, soms kunnen worden teruggebracht tot een eindig, telbaar proces, mits men weet waar te kijken en hoe te tellen. Het resultaat is een nauwkeuriger begrip van de grenzen van berekening, wat een helderder zicht biedt op de grens tussen het mogelijke en het onmogelijke in de wereld van geometrische redenering.