WANI SHINGEN 1962 YA RUSHE A KIMIYYAR KWAMFUTA
Zagayen Hamilton (Hamiltonian cycle) tafiya ce ta zagaye a cikin hanyar sadarwa wadda ke ziyartar kowane maki sau ɗaya tak sannan ta koma farko. A cikin hanyar sadarwa mai alkibla (directed), kowane haɗi kibiya ne da za a iya bi ta hanya ɗaya kawai, kamar titi mai hanya ɗaya. Nau’in wannan matsala mai nauyi shi ne matsalar ɗan kasuwa mai yawo marar daidaito (asymmetric travelling salesman problem).
Yanke shawarar ko irin wannan zagaye yana nan matsala ce mai wahala da ke cikin littattafan karatu. A 1962, Richard Bellman da kuma, daban, Michael Held da Richard Karp sun ba da algorithm na dynamic programming da ke warware ta cikin lokaci kusan 2ⁿ ga hanyar sadarwa mai maki n (har zuwa abubuwan da ke girma daidai gwargwado na polynomial kawai). Fiye da shekaru sittin, babu wanda ya iya yin abin da ya fi wannan a asali ga hanyoyin sadarwa masu alkibla na gama-gari.
Ɗan uwan marar alkibla ya riga ya faɗi
Ga hanyoyin sadarwa masu haɗi na hanya biyu, Andreas Björklund ya karya shingen a 2014 da algorithm na bazuwar da ke gudana cikin 1.657ⁿ, aikin da ya ba shi kyautar EATCS–IPEC Nerode na 2016, bisa ga takardar. Har yanzu shi ne mafi sauri da aka sani ga hanyoyin sadarwa marasa alkibla na gama-gari. Ga masu alkibla, ci gaba ya zo ne kawai ga lokuta na musamman — hanyoyin sadarwa bipartite, hanyoyin sadarwa da ke da ƙananan haɗi a kowane maki — ko ƙarƙashin wani hasashe da ba a tabbatar ba, hasashen asymptotic rank na Strassen.
Sabon iyaka
Tomohiro Koana, na Jami’ar Tokyo, da Soh Kumabe, na kamfanin CyberAgent na Tokyo, yanzu sun ba da algorithm na bazuwar da ke yanke matsalar mai alkibla cikin lokaci
O((375/196)ⁿ) = O(1.9133ⁿ)**.
Ga hanyoyin sadarwa masu alkibla na gama-gari, wannan shi ne ci gaba na farko a tushen exponential tun 1962.
Ƙidaya da mara cikawa da mai cikawa
Wahalar tana da sarƙaƙiya. Ƙidaya zagaye bisa modulo 2 — sanin kawai ko adadinsu mara cikawa ne (odd) ko mai cikawa (even) — ya riga ya yiwu ƙasa da 2ⁿ. Amma adadin zagaye mai cikawa wanda ba sifili ba yana kama da sifili daidai. Gyaran gargajiya shi ne a ba haɗi nauyi na bazuwar ta yadda, a wani jimillar nauyi, mafita ta zama ɗaya tilo (isolation lemma); amma hanyar ƙidaya mara cikawa/mai cikawa mai sauri ba ta iya ɗaukar nauyi ba.
Girke-girken marubutan, a sauƙaƙe:
- A yi hasashen kibiya ɗaya ta zagayen, sannan a nemi a madadin haka hanya ta kowane maki daga ƙarshe ɗaya na wannan kibiya zuwa ɗayan.
- A goge kowace kibiya ba tare da tsari ba da yiwuwar 1/50.
- A kowane maki, a ƙirƙiri rukuni uku na kibiyoyin da ke shigowa, sannan a kwafa kowace kibiya da ta tsira zuwa wani saitin rukuni na bazuwar da ba fanko ba.
- Idan zagaye yana nan, to da yiwuwar aƙalla (49/50)ⁿ⁻¹ ana iya zaɓar rukuni ɗaya a kowane maki ta yadda adadin hanyoyi masu inganci zai zama mara cikawa.
- A ba kowane rukuni — ba kowace kibiya ba — nauyi na bazuwar. Yanzu dabarar isolation tana aiki, kuma kusan maimaitawa (50/49)ⁿ sun isa.
- Kowane maimaitawa yana lissafa ƙidayar mara cikawa ko mai cikawa a kowane jimillar nauyi cikin lokaci (15/8)ⁿ, ta amfani da jimlolin determinant na matrix na Björklund, Kaski da Koutis da kuma wani “linearisation” na bazuwar da Arvind da Guruswami suma suka yi amfani da shi.
A ninka biyun: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ.
Hujja da inji ya samar
Takardar ta ƙare da sanarwa game da AI mai ƙirƙira (generative AI): ChatGPT 6 Astra ce ta samar da hujjar babban theorem kuma ta taimaka wajen tsara rubutun. Marubutan sun ba da bayanan shawarwarin tsaka-tsaki (intermediate propositions), waɗanda ke ba da karatun combinatorial na mafitar asali ta samfurin, sannan suka tabbatar da gyara komai kuma suka ɗauki cikakken alhakin.
Sakamakon na ka’ida ne — ba a gudanar da wani shiri ba — kuma algorithm ɗin na bazuwar ne, da ’yar ƙaramar damar kuskure ta kowace hanya. Tsakanin 1.9133 ga tituna masu hanya ɗaya da 1.657 ga masu hanya biyu, tazarar mai faɗi har yanzu a buɗe take.
