AI TA WARWARE WANI WASAN WUYA NA LAUNUKA

Ɗauki wata hanyar sadarwa ta ɗigogi da aka haɗa da layuka — abin da masana lissafi ke kira graph. Yanzu ka shafa wa ɗigogin launi ta yadda ɗigogi biyu da layi ya haɗa ba za su taɓa samun launi ɗaya ba. Mafi ƙarancin adadin launukan da ke aiki shi ne lambar launi (chromatic number) ta graph ɗin. Wani sanannen misali na musamman shi ne ka’idar launuka huɗu (four-colour theorem), wadda aka tabbatar a 1977, wadda takenta ya faɗi komai: “Every planar map is four colorable” (Kowace taswira a shimfiɗe ana iya shafa mata launuka huɗu).

Cacar Hadwiger ta 1943

A 1943, Hadwiger ya gabatar da wata doka mai faɗi ga dukkan graphs. Ka rage graph ta hanyar share ɗigogi ko layuka, da kuma haɗa ɗigogi biyu da aka haɗa su zama ɗaya. Sakamakon ana kiransa minor. Hadwiger ya duba mafi girman cikakken graph (complete graph) — gungu wanda kowane ɗigo a cikinsa yake haɗe da kowane ɗaya — da za a iya samu ta wannan hanya, kuma ya yi hasashen cewa adadin launukan da ake buƙata ba ya taɓa wuce girman wannan gungu.

Takardar ta kira shi “ɗaya daga cikin matsaloli mafi tsufa kuma mafi tushe a ka’idar graph.” An tabbatar da shi ne kawai ga ƙananan lamura: har zuwa gungu na biyar, inda ya bayyana cewa yana daidai da ka’idar launuka huɗu ko kuma ana iya mayar da shi zuwa gare ta. Daga shida zuwa sama, a buɗe yake.

Kusantowa, logarithm ɗaya bayan ɗaya

Tun da ainihin bayanin ya ƙi bayyana, masu bincike sun yi ƙoƙarin iyakance adadin launuka da wani aiki (function) na girman gungun, wanda ke girma a hankali yadda zai yiwu. Takardar ta ba da labarin ci gaban. Tsawon shekaru da dama, iyaka mafi kyau ta girma ne ɗan sauri fiye da daidaito — da wani abin ninkawa da ya ƙunshi tushen murabba’i na logarithm. ’Yan shekaru da suka wuce, Norin, Postle da Song sun karya wannan shamaki. Delcourt da Postle daga nan sun ƙara inganta shi kuma, mafi muhimmanci, sun nuna cewa ya isa a magance graphs ƙanana-ƙanana. Liu da Luo sun tura ƙarin abin ninkawa ƙasa zuwa logarithm sau uku (triple logarithm).

Ƙarshen da ya dace shi ne hasashen Hadwiger na layi (linear Hadwiger conjecture): wani ninki tsayayye na girman gungun koyaushe ya isa. Wannan ne Sergey Norin, na Jami’ar McGill a Montreal, da Raphael Steiner, na ETH Zurich, yanzu suke iƙirarin sun tabbatar.

Rawar da na’urar ta taka

Marubutan sun fito fili: samfurin OpenAI mai suna GPT-6 Astra ne ya samo hujjar, yana bin umarninsu. Da farko sun roƙe shi ya tabbatar da lamarin graphs masu yawan haɗi ƙwarai, wanda suka yi imani shi ne ɓangaren da ya ɓace. Ya yi nasara, kamar yadda suka rubuta, “bayan ’yan awoyi kaɗan da ɗan ƙarfafawa.” Da aka roƙe shi ya bayyana wani dogaro a fili, ya rufe graphs har zuwa wani girma — amma bai kai cikakken zangon da ake buƙata ba. Daga nan sun roƙe shi wani sabon ra’ayi don cike giɓin, wanda ya haifar da matakin “bootstrap” na hujjar ƙarshe. Kusan babu ɗaya daga cikin ra’ayoyin hujja na musamman na marubutan kansu da ya tsira, in ji su, sai dai wata shawara ɗaya game da matsewa (contractions).

Rubutun na ɗan Adam ne. Wani samfurin OpenAI ya taimaka wajen duba kurakurai da jerin littattafai. Marubutan sun ruwaito cewa Codex na OpenAI ya samar da sigar hujjar gabaɗaya ta ƙa’ida wadda na’ura za ta iya dubawa, a cikin mataimakin hujja na Lean, wanda aka wallafa a intanet tare da wani daftarin farko da AI ta rubuta. Su ne ke ɗaukar cikakken alhakin lissafin.

Cikin hujjar

Hujjar tana da rabi biyu:

1. Ƙananan graphs, launuka kaɗan. Ga graphs da ba su fi iyakar gungun girma da yawa ba, marubutan sun nuna cewa kusan ninki huɗu na girman gungun ya isa. Mafarin shi ne wani sakamako na 1998 na Reed da Seymour: wani sauƙaƙaƙƙen nau’in shafa launi, na “rabe-rabe” (fractional), tuni yana bin dokar layi da abin ninkawa biyu. Sabon aikin yana mayar da shafa launi na rabe-rabe zuwa na gaske ta hanyar ƙara ’yan ƙarin layuka a graph ɗin da kuma samo manyan haɗe-haɗe (matchings) a cikin wani tsari na taimako.
2. Bootstrap. Wata hujja ta biyu tana faɗaɗa zangon girman graphs da aka rufe da abin ninkawa huɗu bisa uku a cikin ma’aunin ƙarfi (exponent) a kowane mataki, a kan farashin wani madaidaici mafi girma. Matakai goma suna kai zangon daga ɗaya bisa uku zuwa kusan 5.92, sama da iyakar 5 da ragewar Delcourt-Postle ke buƙata. Wannan rabin yana amfani da wata tsohuwar dabara ta Gyárfás, wadda marubutan suka ce ba a taɓa amfani da ita kan wannan matsala ba.

Marubutan sun bayyana hujjar a matsayin wadda aka gina daga kayan aikin da aka sani — “tana cikin convex hull na sakamakon da ake da su,” amma ba a wani gefe bayyananne nasa ba.

Abin da ya rage a buɗe

Madaidaicin yana da girma ƙwarai: wani kiyasi na kusa-kusa ya ba da kusan 10¹⁰⁰. Marubutan suna ganin akwai damar sauko da shi ƙasa da 10¹⁰, amma suna tunanin kaiwa, a ce, 100 zai buƙaci sababbin ra’ayoyi. Ainihin hasashen Hadwiger bai taɓu ba: “Ba mu yanke shawara ba,” suka rubuta. Takardar preprint ce; shafuka 41 na sabon lissafi yanzu za su fuskanci binciken wasu masana.