IDAN 1 YA FI 0 TSADA, MATSA BAYANAI YANA ZAMA DA WUYA

Don adana ko aika rubutu a taƙaice, a ba kowace alama (symbol) wata kalma da aka yi da 0 da 1, gajeriya ga alamomin da ke yawan fitowa, doguwa kuma ga waɗanda ba kasafai suke fitowa ba. Dole kalmomin su samar da lambar prefix (prefix code): babu kalmar da za ta zama farkon wata. {0, 10, 11} tana aiki; {0, 01, 11} ba ta aiki, domin 0 shi ne farkon 01. Da lambar prefix, za a iya sake yanka dogon jerin bits zuwa kalmomi ba tare da wani abin raba su ba.

Mafi kyawun irin wannan lamba — wadda ke da mafi ƙarancin matsakaicin tsawo — an same ta a 1952 a aikin D. A. Huffman, da wata dabara mai sauƙi ta kwaɗayi (greedy) da ke gudana da sauri.

Idan haruffa suna da farashi

Dabarar Huffman tana ɗauka cewa tsadar 0 da 1 ɗaya ce. A ce ba haka ba ne: 1 yana ɗaukar lokaci mafi tsawo kafin a aika shi, ko wuri mafi girma kafin a adana shi. Yanzu tsadar kowace kalma jimillar tsadar haruffanta ce, kuma abin da kalma ta ƙunsa yana da muhimmanci kamar tsawonta. Misali, da tsada 1 da 3, 00 da 01 tsawonsu ɗaya amma tsadarsu 2 da 4.

Wannan sigar tana da dogon tarihi. Aikin R. M. Karp na 1961 ya rubuta ta a matsayin matsalar integer programming (shirye-shiryen lambobi cikakku). Ayyukan da suka biyo baya sun samo algorithms na daidai, masu inganci, ga kowane biyu da aka ƙayyade na tsadar lambobi cikakku (integer costs), da kuma tsarin ƙiyasi (approximation scheme) da ke kusantar mafi kyau (optimum) gwargwadon yadda ake so. Amma lokacin da tsadar kanta ke cikin bayanan shigarwa (input), babu wanda ya san wahalar matsalar. Har zuwa 2021, har yanzu an lissafa ta a matsayin tambaya a buɗe.

Amsar: NP-complete

L. Sunil Chandran, na Indian Institute of Science da ke Bengaluru, da Rishikesh Gajjala, na Pramaana Labs, yanzu sun tabbatar cewa yanke hukunci ko akwai lambar da tsadarta ba ta wuce K ba matsala ce NP-complete — ko da tsadar biyu lambobi cikakku ne masu bin juna, M da M + 1. Masana kimiyyar kwamfuta suna kiran matsala NP-complete idan tana da wahala kamar dukan wani iyali na matsaloli na gargajiya: hanya mai sauri ta gaba ɗaya ga ɗaya za ta ba da ita ga dukansu, kuma ba a san ko ɗaya ba. Saboda haka, samo lamba mafi arha matsala ce NP-hard.

Babu saɓani da algorithms masu sauri na tsadar da aka ƙayyade. A cikin hujjar, M yana girma tare da bayanan shigarwa; ga kowane biyun tsada da aka ƙayyade tun farko, waɗannan algorithms har yanzu suna aiki.

Wasan wuyar warwarewa da ke ɓoye a cikin bishiyar lamba

Hujjar ta fara ne daga wata sananniyar matsala mai wahala: a cikin hanyar sadarwa (network) da aka zana a kan takarda ba tare da layuka sun ketare juna ba, za ka iya zaɓar maki k waɗanda babu biyu daga cikinsu da ke haɗe? Sannan ta gina matsalar lamba wadda lambarta mafi arha ke amsa wannan tambaya.

1. Kowace lambar prefix bishiya ce (tree): 0 yana zuwa hagu, 1 zuwa dama. Kalma mai zurfi d mai 1 guda z tana da tsada M × d + z idan tsadar haruffan M da M + 1 ce. Zurfin ne ke ƙayyade babban ɓangaren tsadar, yawan 1 kuma ƙaramin ɓangaren.
2. Marubutan sun ƙirƙiri sabuwar matsala ta tsaka-tsaki: a ƙayyade ganye (leaves) nawa bishiyar ke da su a kowane zurfi, sannan a ba da ƙima (score) ga inda ganyenta suke. Sun nuna cewa bishiya mai arha dole ne, yayin da take girma mataki-mataki, ta gudanar da wani ƙaramin shiri (program) da ke duba makin da aka zaɓa ɗaya bayan ɗaya, yana kwafar kowane zaɓi kuma yana gwada kowace mahaɗa. Duk wata gajeriyar hanya tana ƙara tsada da aƙalla raka’a ɗaya; kowane maki da aka zaɓa yana adana raka’a ɗaya daidai.
3. A ƙarshe, an daidaita yawan fitowar alamomi (frequencies) ta yadda kowace alama ke tilastuwa zuwa zurfin da ya dace, kuma ƙimar ta zama tsadar lambar tare da ƙarin wani adadi tsayayye.

Wani ƙaramin misali daga takardar yana nuna yadda tsadar ke da sarƙaƙiya. Alamomi uku suna da yawan fitowa 20, 12 da 9, kuma tsadar haruffan 83 da 84 ce. Lambar (0, 10, 11) tana da tsada 5,176. Lambar (1, 00, 01) tana da tsada 5,175: ba da harafi mai tsada ga alamar da ta fi yawan fitowa ita ce ke cin nasara, domin sauran kalmomin biyu suna ɗauke da ƙarancin 1.

Inda wahalar take ɓoye

Sakamako na biyu yana nuna inda matsalar take a cikin samar da lamba na yau da kullum (ordinary coding). Dabarar Huffman tana samo mafi gajeren matsakaicin tsawo da sauri. Amma daga cikin dukkan lambobin da suka kai wannan tsawo, zaɓar wadda ke da mafi ƙarancin 1, aka auna su bisa yawan fitowa, ita ma NP-complete ce.

Tambayoyi sun rage: ko matsalar tana ci gaba da wahala idan dukkan lambobi ƙanana ne (abin da ake kira strong NP-hardness), da kuma ko wata hanya mai sauri za ta iya kusantar mafi kyau zuwa kowane daidaito, da lokacin aiki da shi ma ke girma daidai gwargwado tare da wannan daidaito.

Hujjar da aka samo tare da AI

Takardar ta faɗi yadda aka samo ta. Marubutan da farko sun roƙi Codex na OpenAI ya ba da hujjar wahala (hardness proof) ga wata matsala ta gaba ɗaya, sannan suka roƙe shi ya faɗaɗa ta zuwa lambobin da ba na binary ba, a ƙarshe kuma zuwa lambobin binary. Codex ya ba da gudummawa ga dabarar mayarwa (reduction) da ci gabanta na lissafi; ya kuma taimaka wajen rubuta daftari, duba hujjoji da gina misalai. Marubutan sun jagoranci aikin, sun nemi gyare-gyare da sauƙaƙawa, sun sake rubuta bayanin sosai, kuma suna ɗaukar alhakin bayanai da hujjoji na ƙarshe. Kamar kowace preprint, ba a riga an yi mata bitar takwarorin masana (peer review) ba.