AI agent zúžil hľadanie Conwayovho 99-grafu, otvorený problém však nevyriešil

Čo sa podarilo overiť

Conwayov problém sa pýta, či existuje silne regulárny graf s parametrami srg(99,14,1,2). Mal by mať 99 vrcholov, každý so 14 susedmi; každé dva susedné vrcholy by mali práve jedného spoločného suseda a každé dva nesusedné vrcholy presne dvoch. Databáza parametrov silne regulárnych grafov vedená Andriesom Brouwerom naďalej označuje túto kombináciu otáznikom, teda ako prípad bez známej konštrukcie aj bez dôkazu neexistencie. Nový preprint Aaloka Thakkara tento stav nemení, ale prináša niekoľko užších, kontrolovateľných výsledkov.

Najpevnejším z nich je úplné prehľadanie cirkulantných grafov na cyklickej grupe rádu 99. Autor uvádza, že preskúmal všetkých 85 900 584 symetrických množín siedmich dvojíc spojení. V tejto vysoko symetrickej triede nemožno splniť viac než 33 zo 49 tried rozdielov, čo v metrike konferenčnej úlohy zodpovedá 3366 z 4950 podmienok, teda 68 percentám. Rovnaký strop našiel aj pre druhú abelovskú grupu rádu 99. Je to dôkaz o dvoch konkrétnych rodinách kandidátov, nie horná hranica pre všetky grafy na 99 vrcholoch.

Druhý výsledok využíva priamo podmienky lambda = 1 a mí = 2. Po zvolení jedného vrcholu musí jeho 14 susedov vytvárať perfektné párovanie. Zvyšných 84 vrcholov možno priradiť nepárovým dvojiciam z tohto okolia a neznámou časťou zostáva 12-regulárny graf na 84 vrcholoch. Autor túto redukciu zakódoval pre riešič CP-SAT a celý postup skontroloval na známom grafe s parametrami srg(9,4,1,2). Model pre 99 vrcholov však obsahuje približne 380-tisíc booleovských premenných a 761-tisíc obmedzení; v uskutočnených behoch nenašiel riešenie ani nedokázal, že riešenie neexistuje.

Skóre 69,43 percenta nie je časť dôkazu

Najlepší zverejnený artefakt spĺňa 3437 z 4950 hodnotených podmienok, čiže 69,43 percenta. Štrnásť skúšaných konfigurácií zahŕňalo cirkulantné a Cayleyho grafy, MaxSAT, CP-SAT, tabu search, lokálne vyhľadávanie aj evolučné metódy. Výsledky sa sústreďovali okolo 68 až 69,43 percenta a ďalších 1,57 milióna prijatých zmien podľa autora nepridalo ani jednu splnenú podmienku. To podporuje tvrdenie o lokálnom experimentálnom strope použitých postupov, nie o globálnom matematickom maxime.

Rozdiel je zásadný. Skóre nevyjadruje pravdepodobnosť, že Conwayov graf existuje, ani percento dokončenia dôkazu. Plných 4950 bodov by bolo konštrukciou hľadaného grafu; všeobecne dokázaná horná hranica menšia než 4950 by zase znamenala dôkaz neexistencie. Medzi hodnotou 3437 a jedným z týchto dvoch výsledkov preto nevedie jednoduchá cesta, pri ktorej by stačilo postupne dopĺňať chýbajúce percentá. Podmienky spoločných susedov sú navzájom previazané a lokálna oprava môže poškodiť viacero iných vzťahov.

Práca skúšala aj grafy s predpísanými automorfizmami. Nezávislá staršia štúdia Patricka Cesarza a Andrewa Woldara dokázala, že prípadný Conwayov graf by mal veľmi obmedzenú grupu symetrií: deliteľnosť jej rádu siedmimi vynucuje cyklickú grupu rádu sedem a párny rád pripúšťa iba malé možnosti. Thakkar preto vytvoril orbitový model okrem iného pre akciu rádu sedem s jedným pevným bodom. Ani 48-hodinový beh na 14 jadrách však tento podprípad nerozhodol. Takýto výsledok je užitočný ako správa o limite konkrétneho nástroja, nie ako vylúčenie danej symetrie.

Koľko výskumu urobila AI

Označenie „autonómny AI výskumný agent“ potrebuje spresnenie. Kontrolný formulár pripojený k preprintu uvádza, že tému, základnú stratégiu, voľbu prístupov a požiadavku na preštudovanie literatúry určil autor. Agent potom v opakovaných cykloch vytváral implementácie, formulácie obmedzení, redukcie a koncept rukopisu. Vývoj hypotéz a interpretáciu výsledkov práca hodnotí prevažne ako ľudské s asistenciou AI, zatiaľ čo implementáciu experimentov a písanie opisuje ako prevažne vykonané AI s ľudskou pomocou.

Dokumentácia pomenúva aj použitý systém: jazykový model pracoval cez nástrojové rozhranie s prístupom k shellu a volal externé riešiče Google OR-Tools CP-SAT a Microsoft Z3 spolu s vedeckými knižnicami. Autor medzi pozorovanými slabinami uvádza opakovaný sklon systému preceňovať výsledky alebo príliš široko formulovať závery. Ľudské zásahy smerovali k užším tvrdeniam, ktoré možno skontrolovať enumeráciou, samostatným verifikátorom alebo klasickým argumentom. Presnejšie je preto hovoriť o agentickom výpočtovom výskume pod odborným vedením než o úplne samostatnom AI matematikovi.

Táto transparentnosť je dôležitejšia než samotná nálepka autonómnosti. Pri otvorenom matematickom probléme nemá plynulé vysvetlenie modelu dôkazovú hodnotu. Presvedčivý výstup musí obsahovať presnú formuláciu prehľadaného priestoru, kód, artefakt a spôsob nezávislej kontroly. Preprint deklaruje sprístupnenie enumerátora, redukčného riešiča, orbitových modelov, vyhľadávacieho rámca a najlepšieho artefaktu v doplnkových materiáloch. Nezávislá reprodukcia týchto výpočtov však zostáva ďalším krokom, ktorý samotné autorské vyhlásenie nenahrádza.

Význam pre slovenský a európsky výskum

Pre slovenské a európske univerzitné tímy je zaujímavý najmä pracovný model, nie vyriešenie konkrétneho grafu. Agent dokáže rýchlo prekladať matematické podmienky do SAT alebo CP-SAT formulácií, skúšať alternatívne reprezentácie a pripravovať verifikovateľné kandidáty. Použité riešiče a základné vedecké knižnice sú verejne dostupné, takže podobný postup nie je principiálne viazaný na veľké proprietárne laboratórium. Náročnejšou časťou ostáva odborná kontrola ekvivalencie redukcie, úplnosti enumerácie a správnosti verifikátora.

Praktický dôsledok presahuje kombinatoriku. Rovnaké zásady sa dajú uplatniť pri optimalizácii rozvrhov, verifikácii softvéru, návrhu sietí alebo formálnom overovaní hardvéru: jazykový agent môže navrhovať experimenty, ale rozhodujúci výsledok má vytvoriť deterministický nástroj alebo kontrolovateľný certifikát. Menšie európske pracoviská tak môžu získať produktívneho pomocníka pri programovaní a orientácii v priestore metód bez toho, aby museli akceptovať jeho text ako autoritu.

Otvorené zostávajú tri hlavné neistoty. Prvou je nezávislé zopakovanie deklarovaných úplných výpočtov a kontrola zverejneného artefaktu. Druhou je miera skutočnej autonómnosti, pretože počet ľudských rozhodnutí, zamietnutých návrhov a korekcií nemožno vyčítať iba z výsledného článku. Treťou je vedecký dosah: redukcia a negatívne výsledky pre symetrické triedy môžu byť užitočnou infraštruktúrou, no zatiaľ neukazujú, či sa všeobecná existenčná otázka priblížila k rozhodnutiu. Conwayov 99-graf teda ostáva otvoreným problémom a najcennejším prínosom práce je testovateľný záznam toho, čo agent, človek a klasické riešiče dokázali aj nedokázali.