HAƊA SAƘONNI YA FI TURA SU A HANYOYINSU, BAYAN SHEKARU 22 NA SHAKKA

Ka yi tunanin hanyar sadarwa ta kebul inda masu aikawa da dama kowannensu yake son isa ga mai karɓarsa. Hanyar gargajiya ita ce routing (tura saƙo a hanya): kowane saƙo yana tafiya kamar kunshin kaya a kan hanya ɗaya ko fiye, kuma ana iya ma raba zirga-zirga a hanyoyi da yawa a kowane rabo. Network coding (sanya code a hanyar sadarwa) tana ƙara wani ’yanci: mahaɗai na tsakiya za su iya haɗa saƙonnin da suka karɓa — misali ta hanyar haɗa su da lissafi — maimakon kawai su tura su gaba.

Tambayar ita ce ko wannan ’yancin yana taɓa barin ƙarin bayanai su wuce. Takardar ta mai da hankali kan hanyoyin sadarwa marasa alƙibla (undirected), inda kebul zai iya ɗaukar bayanai a kowace alƙibla amma alƙiblolin biyu suna raba iyaka ɗaya.

Hasashen da aka tabbatar a wani lamari bayan wani

A 2004, Li da Li sun yi hasashen cewa a wannan yanayi code ba ya kawo wani fifiko a kan fractional routing (tura saƙo da aka raba); Harvey, Kleinberg da Rasala Lehman sun tsara hasashen guda daban. A cikin shekaru ashirin masu zuwa an tabbatar da shi ga wani rukunin hanyoyin sadarwa bayan wani — zama biyu (two sessions), wasu hanyoyin sadarwa masu shimfiɗa (planar), hanyoyin sadarwa masu mahaɗai na code shida a mafi yawa, da ƙari — amma ba a taɓa warware shi gaba ɗaya ba. Wasu sakamako a ka’idar sarƙaƙiya (complexity theory), kamar ƙananan iyakoki ga tsara lambobi a ƙwaƙwalwar waje da kuma ga da’irorin ninkawa, an ma tabbatar da su ne bisa zaton sa.

Ka’idar da aka sani ta riga ta iyakance abin da ke cikin haɗari: code zai iya fin routing da ninki na logarithm a mafi yawa. Kuma wani sakamako na 2017 na Braverman, Garg da Schvartzman ya nuna cewa hanyar sadarwa guda ɗaya mai fifikon code na zahiri za a iya faɗaɗa ta zuwa wani giɓi mafi girma sosai. Duk abin ya dogara ne kan nemo misali ɗaya mai iyaka.

Haɗa lissafi ya isa

Ƙarin bayanin (appendix) ya ba da na’urar asali, wadda ke nuna dalilin da ya sa haɗawa za ta iya taimakawa. Sanya masu aikawa da dama a kewayen wata cibiya v, masu karɓarsu a kewayen wata cibiya w, kuma haɗa v da w da kebul ɗaya. Kowane mai aikawa kuma yana da ƙananan hanyoyin gefe zuwa sauran masu karɓa. A zagaye uku, kebul ɗin tsakiya yana ɗaukar jimillar dukan saƙonni; kowane mai karɓa yana samun wannan jimillar tare da sauran saƙonnin daga hanyoyin gefe, kuma yana dawo da nasa ta hanyar cirewa. Ba tare da kebul ɗin tsakiya ba, kowane mai aikawa yana da tsalle biyar daga mai karɓarsa.

Wannan na’urar, daga aikin baya na Haeupler, Wajc da Zuzic, tana sa code ya fi sauri, amma ita kaɗai ba ta iya ɗaukar ƙari: doguwar hanya har yanzu za ta iya gudanar da bututun (pipeline) mai saurin gudana.

Da’ira da aka mayar hanyar sadarwa

Xindan Zhang da Baochun Li, na Jami’ar Toronto, da Zongpeng Li, na Jami’ar Tsinghua, sun gano matakin da ya ɓace. Suna mayar da wani gajeren code zuwa lissafi mai juyawa (reversible computation) — da’ira ta haɗa lambobi masu juyawa da ke yin lissafi, kwafin sakamakon, sannan su warware aikin tsakiya. Sannan su gina sabuwar hanyar sadarwa wadda kebul ɗinta na zahiri su ne wayoyin wannan da’irar, kuma su ba kowane register na lissafin, har da registers na rubutun wucin gadi, buƙatarsa ta mai aikawa da mai karɓa.

Lissafi mai kyau na “lokaci” a kan wayoyin yana yin sauran. Idan aka tara a dukan wayoyi, tsawon ya yi daidai da mafi ƙarancin nisan da buƙatun dole su rufe. Amma buƙatun da aka ayyana ba za su iya guje wa wasu ƙofofi (gates) da ke cin ƙarin raka’a biyu ba. Don haka dole routing ya gaza cikakken saurin gudana, yayin da code ke amfani da kowane kebul sau ɗaya daidai kuma, idan aka yi bututu a kan tubali da yawa, yana kusantar saurin gudana na ɗaya.

Abin da aka tabbatar

• Hanyar sadarwa mai iyaka da ke haɗe, inda kowane mahaɗi ke haɗe da wasu uku a mafi yawa da iyaka ta raka’a ɗaya a kowane kebul, inda wani sauƙaƙan binary linear code ke doke mafi kyawun fractional routing da zai yiwu. Hasashen 2004 ƙarya ne.
• Ginin lambobi guda yana aiki a kan kowane finite field da kowane finite abelian group mara sauƙi a lokaci guda.
• Ta hanyar haɗa kwafi akai-akai, masu binciken sun gina dangin hanyoyin sadarwa marasa iyaka inda code ke kusantar cikakken saurin gudana yayin da routing ke faɗuwa kamar power na 1/log n — fifikon polylogarithm.

Takardar ba ta ba da adadin mahaɗai a cikin misalinta na karyatawa ba. Tubalin gininsa kaɗai code ne da ke ɗaukar zagaye 13,122.

Inji ya tantance

Dukan misalin karyatawa mai iyaka da ka’idar dangin an tsara su a cikin mataimakin hujja Lean. A cewar masu binciken, binciken sanarwa 2,472 da ka’idoji 1,755 ya nuna cewa hujjojin suna amfani da axiom uku na yau da kullum na Lean kawai, ba tare da hujjoji marasa cika ba; wani sake dubawa mai zaman kansa a cikin sabon muhalli shi ma ya yi nasara, ko da yake da kernel ɗin Lean guda.

Abin da ya rage a buɗe

Masu binciken sun lissafa tambayoyi uku: ainihin girman fifikon a misalinsu mai iyaka, ko ana kaiwa ga sananniyar silin ta logarithm a zahiri, da kuma ko akwai ƙaramin misalin karyatawa. Jumlarsu ta ƙarshe ta taƙaita inda abubuwa suke: “Code, ya bayyana, yana taimakawa a hanyoyin sadarwa marasa alƙibla; nawa zai iya taimakawa ya rage a gani.”

Bayyana amfani da AI. Wani bayanin ƙasan shafi ya bayyana cewa GPT-6 Astra na OpenAI ya taimaka wajen haɓaka hujjojin da code ɗin Lean.