AI YATEGUA FUMBO LA KUPAKA RANGI

Chukua mtandao wa nukta zilizounganishwa kwa mistari — kile wanahisabati wanachokiita grafu. Sasa paka rangi nukta hizo ili nukta mbili zilizounganishwa kwa mstari zisiwe kamwe na rangi moja. Idadi ndogo kabisa ya rangi inayowezesha hilo ni namba ya kromatiki ya grafu. Kesi maalum maarufu ni nadharia ya rangi nne, iliyothibitishwa mwaka 1977, ambayo kichwa chake kinasema yote: “Every planar map is four colorable” (Kila ramani bapa inaweza kupakwa rangi nne).

Dau la Hadwiger la 1943

Mwaka 1943, Hadwiger alipendekeza kanuni pana kwa grafu zote. Punguza grafu kwa kufuta nukta au mistari, na kwa kuunganisha nukta mbili zilizounganishwa kuwa moja. Matokeo yanaitwa grafu-ndogo (minor). Hadwiger aliangalia grafu kamili kubwa zaidi — kundi ambamo kila nukta imeunganishwa na kila nyingine — inayoweza kupatikana kwa njia hii, na akakisia kwamba idadi ya rangi zinazohitajika haizidi kamwe ukubwa wa kundi hilo.

Makala inaliita “miongoni mwa matatizo ya zamani zaidi na ya msingi zaidi katika nadharia ya grafu”. Limethibitishwa kwa kesi ndogo tu: hadi makundi ya tano, ambapo linabainika kuwa sawa na nadharia ya rangi nne au linaweza kurejeshwa kwake. Kuanzia sita na kuendelea, liko wazi.

Kukaribia, logariti moja baada ya nyingine

Kwa kuwa kauli halisi inakataa kuthibitishwa, watafiti walijaribu kufunga idadi ya rangi kwa kitendakazi fulani cha ukubwa wa kundi, kinachokua polepole kadiri iwezekanavyo. Makala inasimulia maendeleo. Kwa miongo mingi, kikomo bora kilikua kwa kasi kidogo kuliko uwiano wa moja kwa moja — kwa kigawo kinachohusisha kipeuo cha pili cha logariti. Miaka michache iliyopita, Norin, Postle na Song walivunja kizuizi hicho. Delcourt na Postle kisha walikiboresha zaidi na, muhimu kabisa, wakaonyesha kwamba inatosha kushughulikia grafu ndogo kiasi. Liu na Luo walishusha kigawo cha ziada hadi logariti ya mara tatu.

Kituo cha mwisho cha kawaida ni dhana ya Hadwiger ya mstari: kigawe kisichobadilika cha ukubwa wa kundi hutosha daima. Hilo ndilo Sergey Norin, wa Chuo Kikuu cha McGill huko Montreal, na Raphael Steiner, wa ETH Zurich, sasa wanadai kulithibitisha.

Mchango wa mashine

Waandishi wako wazi: uthibitisho ulipatikana na GPT-6 Astra, modeli ya OpenAI, ikifuata maelekezo yao. Kwanza waliiomba ithibitishe kesi ya grafu zilizosongamana sana, ambayo waliamini ndiyo kipande kilichokosekana. Ilifanikiwa, wanaandika, “baada ya saa kadhaa tu na kutiwa moyo kidogo”. Ilipoombwa kuweka wazi utegemezi mmoja, ilishughulikia grafu hadi ukubwa fulani — lakini si kabisa wigo uliohitajika. Kisha waliiomba wazo asilia la kuziba pengo, na hilo likazaa hatua ya “kujiinua” (bootstrap) ya uthibitisho wa mwisho. Karibu hakuna wazo mahususi la uthibitisho la waandishi wenyewe lililosalia, wanasema, isipokuwa pendekezo moja kuhusu ukandamizaji (contractions).

Uandishi ni wa binadamu. Modeli nyingine ya OpenAI ilisaidia katika kusahihisha na orodha ya marejeo. Waandishi wanaripoti kwamba Codex ya OpenAI ilitengeneza toleo rasmi, linaloweza kuhakikiwa na mashine, la uthibitisho mzima katika msaidizi wa uthibitisho Lean, lililowekwa mtandaoni pamoja na rasimu ya awali iliyoandikwa na AI. Wanachukua jukumu kamili kwa hisabati yenyewe.

Ndani ya uthibitisho

Hoja ina nusu mbili:

1. Grafu ndogo, rangi chache. Kwa grafu zisizo kubwa sana kuliko kikomo cha kundi, waandishi wanaonyesha kwamba takriban mara nne ya ukubwa wa kundi hutosha. Mahali pa kuanzia ni tokeo la mwaka 1998 la Reed na Seymour: aina iliyolegezwa, ya “sehemu” (fractional), ya kupaka rangi tayari inatii kanuni ya mstari kwa kigawo cha mbili. Kazi mpya inageuza upakaji rangi wa sehemu kuwa upakaji rangi halisi kwa kuongeza mistari michache kwenye grafu na kupata uoanishaji (matchings) mkubwa mno katika muundo saidizi.
2. Kujiinua. Hoja ya pili inapanua wigo wa ukubwa wa grafu unaoshughulikiwa kwa kigawo cha nne-theluthi katika kipeo kwa kila hatua, kwa gharama ya kisabiti kikubwa zaidi. Hatua kumi zinapeleka wigo kutoka theluthi moja hadi takriban 5.92, kupita kizingiti cha 5 kinachohitajika na upunguzaji wa Delcourt-Postle. Nusu hii inatumia mbinu ya zamani ya Gyárfás, ambayo waandishi wanasema haikuwahi kutumika kwa tatizo hili.

Waandishi wanaueleza uthibitisho kama uliojengwa kwa zana zinazojulikana — “uliomo ndani ya ganda mbinuko la matokeo yaliyopo”, lakini si kwenye ukingo wake ulio dhahiri.

Kinachobaki wazi

Kisabiti ni kikubwa mno: makadirio ya jumla yanatoa takriban 10¹⁰⁰. Waandishi wanaona nafasi ya kukishusha chini ya 10¹⁰, lakini wanadhani kufikia, tuseme, 100 kungehitaji mawazo mapya. Dhana halisi ya Hadwiger haijaguswa: “Hatujaamua”, wanaandika. Makala ni chapisho la awali; kurasa 41 za hisabati mpya sasa zitakabiliwa na uchunguzi wa wataalamu wengine.