JERAWA DUK DA KWATANCEN DA AKA HANA, KUSAN DA SAURI IRI ƊAYA
Don jera abubuwa n ta hanyar kwatanta su biyu-biyu, kusan kwatance n log n dole ne kuma sun isa. Amma hakan yana ɗauka cewa za a iya kwatanta kowane abu biyu.
Sau da yawa ba za a iya ba. Marubutan sun aro wani misali daga wata takarda ta 2011: masu neman aiki da dama suna neman aiki ɗaya, kuma dukansu suna da masu ba da shaida (references). Za a iya kwatanta masu neman aiki biyu ne kawai idan wani mai ba da shaida ya san su duka biyun. Kwatancen da aka yarda da su suna samar da wata hanyar sadarwa (network), wato zane-zanen haɗi (graph): kowane abu maki ne, kowane kwatance da aka yarda da shi kuma haɗi ne. Ainihin jerin a ɓoye yake, amma an tabbatar cewa graph ɗin yana ɗauke da shi, a matsayin wata hanya (path) da ke haɗa kowane abu da wanda ke biye da shi. Tambayar: kwatance nawa ake buƙata don gano jerin? Wannan shi ne jerawa ta gama-gari (generalized sorting).
Dalilin da dabarun da aka saba ke kasawa
Algorithms na gargajiya sun dogara ne da ’yancin zaɓi. QuickSort yana zaɓar wani “ginshiƙi” (pivot) ya kwatanta shi da yawancin sauran abubuwa, amma a graph na kowane iri zai yiwu babu wani abu da ke haɗe da yawancin sauran. MergeSort yana raba abubuwan zuwa rukunoni ya jera kowanne, amma wani rukuni zai iya kasancewa ba za a iya jera shi shi kaɗai ba: abubuwa biyu da ke maƙwabtaka a jerin ƙarshe ba lallai ne su kasance a haɗe a cikinsa ba. A tushe ma, jerawa ta yau da kullum koyaushe tana da wani kwatance da ake iya yi wanda ke kawar da kaso mai kyau na jerin da ka iya yiwuwa; da ƙayyadaddun kwatance, mai yiwuwa babu ko ɗaya.
Ci gaba ya yi jinkiri. A 2011, Zhiyi Huang, Sampath Kannan da Sanjeev Khanna sun gano wata hanya da ke amfani da kusan kwatance n¹·⁵, idan ba a lissafa abubuwan logarithm (logarithmic factors) ba, kuma wannan iyaka (bound) ta tsaya ga graph na kowane iri tun daga lokacin. Har sun tambaya ko matsalar za ta iya kasancewa mafi wuya a tushe fiye da jerawa ta yau da kullum, ta yadda za ta buƙaci n da aka ɗaga zuwa ƙarfin (power) da ya wuce 1.
Fara hasashe, sannan a gyara daga baya
Sanjeev Khanna, daga Jami’ar New York (New York University), Aaron Putterman, daga Jami’ar Harvard, da Junkai Song, daga Jami’ar New York kamar Khanna, yanzu sun amsa wannan tambaya: a’a. Algorithm ɗinsu mai amfani da bazuwar zaɓi (randomised) yana jerawa da kusan kwatance n log⁴ n a matsakaici, a kan kowane graph — abubuwan logarithm ’yan kaɗan ne kawai sama da jerawa ta yau da kullum. Kuma, kamar yadda suka rubuta, yana da “sauƙi in an kwatanta” (relatively simple). Sai dai ribar ta ka’ida ce (theoretical): tsayayyun lambobin (constants) hujjar suna da matuƙar girma (abubuwan ninkawa kamar 2³²), don haka fa’idar tana bayyana ne kawai ga n mai girma sosai.
Ya ginu ne a kan wani sakamako sananne: idan aka ba da hasashen alƙiblar kowane haɗi, wanda ya yi kuskure a kan w daga cikinsu, za a iya dawo da jerin da kusan kwatance n log n + w. Don haka aikin ya zama samar da hasashe mai ƙarancin kurakurai ta amfani da ƙarancin kwatance. Muhimman matakai:
- Hasashe na farko mara cikakken daidaito. A kwatanta wani samfurin bazuwa (random sample) na nau’i-nau’i da ke haɗe, sannan a zaɓi kowane jeri da ya dace da amsoshin. Yana yin kurakurai da yawa, amma ba masu yawa fiye da kima ba.
- A keɓe kurakuran, maimakon a gyara su. Maimakon gyara hasashen da ba daidai ba, algorithm ɗin yana nemo sassan graph ɗin da kurakurai suka fi yawa a cikinsu fiye da matsakaici, sannan ya ajiye su gefe. Kowane zagaye yana rage sauran kurakuran zuwa kashi ɗaya cikin huɗu, bisa ga abin da ake tsammani (in expectation).
- A dawo daga baya. Ana kula da haɗin da aka ajiye gefe a wani mataki (phase) na gaba. Kowane mataki yana warware aƙalla rabin haɗin da ke jiran warwarewa, don haka kusan matakai ashirin sun isa ga haɗi miliyan ɗaya.
Hujja da aka samo da taimakon injuna
Bayanin da takardar ta bayar game da amfani da ƙirƙirarriyar basira (AI) yana da filla-filla fiye da yadda aka saba. Ta bayyana cewa ChatGPT 6-Astra “ya kasance mai matuƙar muhimmanci wajen tabbatar da ingantattun iyakoki (improved bounds)”. Wani samfuri (model) ya fara samo wani algorithm da ke amfani da kusan kwatance n¹·³³, sannan ya tsaya cak. Marubutan sun kai shi zuwa n¹·²; sannan, bayan an ba su umarni (prompts) sau goma-goma a cikin makonni da dama, samfuran sun sami ci gaba a jere — n^(10/9), n^(17/16), n^(19/18) — kafin su kai ga algorithm kusan na layi (near-linear). Marubutan sun ƙara da cewa ba a sani ba ko matakinsu na tsakiya ya zama dole ga wannan bincike na ƙarshe.
Abin da har yanzu yake a buɗe
Sakamakon yana ƙirga kwatance ne, ba lokacin lissafin kwamfuta ba: kamar yadda aka bayyana shi, algorithm ɗin ba ya gudana a lokacin polynomial (polynomial time), alhali hanyar 2011 tana yi. Marubutan sun lissafa tambayoyi uku da ke a buɗe: ko za a iya cire sauran abubuwan logarithm, ko algorithm mara bazuwar zaɓi (randomness) zai iya yin kyau haka, da kuma ko wani algorithm mai inganci (efficient) zai iya kaiwa adadin kwatance iri ɗaya — ko ma ya doke n¹·⁵ kwata-kwata.
