FAIFAN AJIYA CIKAKKE DA AKA ARO YANA SA KWAMFUTOCI SU FI SAURI
Wasu matsaloli suna da arha a lokaci amma suna da kwaɗayin ƙwaƙwalwa, wasu kuma akasin haka. Ga wasu ayyuka na asali kaɗan, masana ka’idoji sun tabbatar da iyakoki masu tsauri kan wannan musaya: da ƙaramar ƙwaƙwalwar aiki, ba za ka iya yin sauri ba. Wata sabuwar takarda ta nuna cewa wani baƙon tushe, ƙwaƙwalwa da ta riga ta cika kuma dole a mayar da ita lafiya, yana karya waɗannan iyakoki.
Faifan ajiya da aka aro
Ana kiran samfurin catalytic computing, wanda Buhrman, Cleve, Koucký, Loff da Speelman suka gabatar a 2014. Wani algorithm yana samun ƙaramar ƙwaƙwalwa mai tsabta, kusan bits log n ga shigarwa mai girman n, tare da babbar ƙwaƙwalwa mai datti da ta riga ta cika da bayanai na bazuwar da bai zaɓa ba. Zai iya amfani da su biyun yadda ya ga dama, amma idan ya tsaya, kowane bit na ƙwaƙwalwa mai datti dole ya kasance daidai kamar yadda yake a da.
Marubutan suna amfani da misalin da aka saba: ka ari babban faifan ajiya na abokinka, cike da tunawa na dijital masu daraja, don gudanar da wani lissafi. Ba ka son rasa aboki, don haka kana mayar da kowane bit idan ka gama.
Da farko an yi samfurin ne don tabbatar da cewa irin wannan ƙwaƙwalwa ba ta da amfani. A hankali, don mayar da komai dole ka riƙe dukkan bayanai, don haka ba za ka taɓa samun ƙarin wuri ba. Abin mamaki, akasin haka ne ya zama gaskiya: cikakkiyar ƙwaƙwalwa tana ba ka damar warware matsalolin da babu wanda ya san yadda ake warware su da ƙwaƙwalwa mai tsabta kaɗai. Amma waɗannan sakamakon sun shafi wuri (space), kuma algorithms ɗin suna da jinkiri ƙwarai.
Fiye da abin da aka tabbatar zai yiwu
Adelmo Morrison Orozco, Nathan Sheffield da Ryan Williams (MIT) yanzu suna duba sauri. Da ƙwaƙwalwa mai tsabta ta logarithm da ƙwaƙwalwa da aka aro mai girman polynomial, sun ba da algorithms waɗanda:
- suke jera jeri da lissafa discrete Fourier transform a lokaci n^(1+o(1)), kusan na layi;
- suke ninka matrices a lokaci n^(ω+o(1)), da sauri kamar mafi kyawun hanyar da aka sani mai ƙwaƙwalwa marar iyaka.
Ba tare da faifan da aka aro ba, an tabbatar cewa haɗin lokaci da ƙwaƙwalwa dole ya kasance aƙalla kusan n² ga jerawa da Fourier transform, da n³ ga ninka matrices. Don haka waɗannan algorithms na catalytic suna kai wa gudun da babu wani algorithm na yau da kullum mai ƙaramar ƙwaƙwalwa da zai iya kai wa. Marubutan sun kira shi nunin farko marar sharaɗi cewa algorithms na catalytic sun fi takwarorinsu marasa catalytic.
Juyawa, karantawa, warwarewa
Babban sinadarin wata gajeriyar dabarar haɗe-haɗe (combinatorial) ce. A ce wani algorithm zai iya juya wani ɓangare na ƙwaƙwalwa da aka aro tsakanin wata ƙima da ba a sani ba τ da τ + x, inda x shi ne sakamakon da yake so. A cikin wani babban teburin “mataimaki”, shi ma aro, ƙara 1 a kan wasu wurare da aka zaɓa da kyau. Wurin da ke matsayi τ yana ƙaruwa da ɗaya idan kuma sai idan x yana cikin wani tarin da aka bayar. Sannan a gudanar da kowane mataki a baya-baya, sai faifan ya koma yadda yake, sai dai ɗan amsar da kake so.
Tara wannan dabarar mataki-mataki yana tantance da’irori marasa zurfi (shallow circuits) cikin sauri. Daga nan marubutan suka sake bayyana hanyoyin sadarwar jerawa (sorting networks), fast Fourier transforms da ninka matrices mai sauri a matsayin irin waɗannan da’irori. Ga lissafi, matakan da ke ninka abubuwa biyu da ba a sani ba ne kawai ke ƙara kuɗi; matakan layi zalla kusan kyauta suke.
Kwatanci na adalci
Wata suka: iyakokin gargajiya suna ɗauka cewa ana rubuta amsar sau ɗaya, daga hagu zuwa dama, a kan wani tef na fitarwa daban, alhali algorithms na catalytic suna rubuta amsarsu a cikin faifan da aka aro. Takardar ta magance hakan. Marubutan sun nuna cewa algorithms ɗinsu za su iya rubuta amsar a zagaye biyu a kan tef na fitarwa, kuma ga algorithms na yau da kullum zagaye biyu ba su fi ɗaya taimako ba. Don haka iyakokin har yanzu suna aiki, kuma rabuwar ta tabbata. Sun kuma tabbatar cewa zagaye ɗaya bai isa ba ko da da faifan da aka aro: jerawa a lokacin tana fuskantar shingen n² iri ɗaya.
Dogon jerin masu amfana
Kayan aiki iri ɗaya suna ba da algorithms na catalytic masu sauri don ninka manyan lambobi cikakku (integers) da polynomials, ƙirga triangles da nemo cliques a cikin hanyoyin sadarwa, gano hanyoyi da zagaye (cycles), da daidaita tsarin rubutu da alamomin wildcard. Lokutan gudanarsu sun yi daidai, har zuwa ƙananan abubuwa, da mafi kyawun algorithms da aka sani waɗanda ke da duk ƙwaƙwalwar da suke so. A kowane hali, ƙwaƙwalwa da aka aro dole ta dawo daidai kamar yadda aka ba da ita aro.