1 INAPOGHARIMU ZAIDI YA 0, KUBANA DATA KUNAKUWA KUGUMU

Ili kuhifadhi au kutuma maandishi kwa ufupi, ipe kila alama neno lililoundwa kwa 0 na 1, fupi kwa alama zinazojitokeza mara nyingi na refu zaidi kwa zile adimu. Maneno hayo lazima yaunde msimbo wa kiambishi awali (prefix code): hakuna neno linaloweza kuwa mwanzo wa neno jingine. {0, 10, 11} unafaa; {0, 01, 11} haufai, kwa kuwa 0 ndio mwanzo wa 01. Kwa msimbo wa kiambishi awali, mfuatano mrefu wa biti unaweza kukatwa tena kuwa maneno bila kitenganishi chochote.

Msimbo bora kabisa wa aina hiyo — ule wenye urefu wa wastani mdogo zaidi — ulipatikana mwaka 1952 na D. A. Huffman, kwa mbinu rahisi ya pupa (greedy) inayofanya kazi haraka.

Herufi zinapokuwa na bei

Mbinu ya Huffman inadhani kwamba 0 na 1 zinagharimu sawa. Tuseme hazigharimu sawa: 1 inachukua muda mrefu zaidi kusafirishwa, au nafasi zaidi kuhifadhiwa. Sasa kila neno linagharimu jumla ya herufi zake, na muundo wa neno ni muhimu sawa na urefu wake. Kwa gharama 1 na 3, kwa mfano, 00 na 01 zina urefu sawa lakini zinagharimu 2 na 4.

Toleo hili lina historia ndefu. R. M. Karp aliliandika kama tatizo la upangaji wa namba kamili (integer programming) mwaka 1961. Kazi za baadaye zilipata algoriti kamili na zenye ufanisi kwa jozi yoyote isiyobadilika ya gharama za namba kamili, pamoja na mpango wa ukadiriaji (approximation scheme) unaokaribia kiwango bora kadiri inavyotakiwa. Lakini gharama zenyewe zinapokuwa sehemu ya ingizo (input), hakuna aliyejua tatizo lilikuwa gumu kiasi gani. Hata mwaka 2021, bado liliorodheshwa kama swali lililo wazi.

Jibu: NP-kamili

L. Sunil Chandran, wa Indian Institute of Science huko Bengaluru, na Rishikesh Gajjala, wa Pramaana Labs, sasa wanathibitisha kwamba kuamua kama upo msimbo wenye gharama isiyozidi K ni NP-kamili (NP-complete) — hata pale gharama hizo mbili ni namba kamili zinazofuatana, M na M + 1. Wanasayansi wa kompyuta huliita tatizo NP-kamili linapokuwa gumu sawa na familia nzima ya matatizo maarufu: mbinu ya jumla ya haraka kwa mojawapo ingetoa mbinu kwa yote, na hakuna inayojulikana. Kwa hiyo kupata msimbo wa bei nafuu zaidi ni NP-gumu (NP-hard).

Hakuna mgongano na algoriti za haraka za gharama zisizobadilika. Katika uthibitisho, M huongezeka pamoja na ingizo; kwa jozi yoyote ya gharama iliyowekwa mapema, algoriti hizo bado zinatumika.

Fumbo lililofichwa katika mti wa usimbaji

Uthibitisho unaanza na tatizo gumu linalojulikana: katika mtandao uliochorwa kwenye karatasi bila mistari kukatana, je, unaweza kuchagua nukta k ambazo hakuna mbili kati yake zilizounganishwa? Kisha unajenga tatizo la usimbaji ambalo msimbo wake wa bei nafuu zaidi unajibu swali hilo.

1. Msimbo wowote wa kiambishi awali ni mti: 0 huenda kushoto, 1 huenda kulia. Neno la kina d lenye herufi 1 zipatazo z linagharimu M × d + z herufi zinapogharimu M na M + 1. Kina huamua sehemu kubwa ya gharama, na idadi ya 1 huamua sehemu ndogo.
2. Waandishi wanabuni tatizo jipya la kati: weka idadi ya majani ambayo mti unayo katika kila kina, na utoe pointi kulingana na mahali majani yake yalipo. Wanaonyesha kwamba mti wa bei nafuu lazima, unapokua ngazi kwa ngazi, uendeshe programu ndogo inayokagua nukta zilizochaguliwa moja baada ya nyingine, inayonakili kila chaguo na kujaribu kila kiungo. Njia yoyote ya mkato inagharimu angalau kipimo kimoja zaidi; kila nukta inayochaguliwa huokoa kipimo kimoja hasa.
3. Mwishowe, marudio (frequencies) yanarekebishwa ili kila alama ilazimishwe kukaa kwenye kina sahihi, na jumla ya pointi inakuwa gharama ya usimbaji pamoja na kiasi kisichobadilika.

Mfano mdogo kutoka kwenye makala unaonyesha jinsi gharama hizi zilivyo za hila. Alama tatu zina marudio 20, 12 na 9, na herufi zinagharimu 83 na 84. Msimbo (0, 10, 11) unagharimu 5,176. Msimbo (1, 00, 01) unagharimu 5,175: kuipa alama inayojitokeza mara nyingi zaidi herufi ghali kunashinda, kwa sababu maneno mengine mawili kisha yanabeba 1 chache zaidi.

Mahali ugumu unapojificha

Tokeo la pili linaonyesha kwamba tatizo liko ndani ya usimbaji wa kawaida wenyewe. Mbinu ya Huffman hupata urefu mfupi zaidi wa wastani haraka. Lakini kati ya misimbo yote inayofikia urefu huo, kuchagua ule wenye 1 chache zaidi, zikipimwa kwa marudio, nako ni NP-kamili.

Maswali yanabaki: je, tatizo linabaki gumu pale namba zote ni ndogo (kinachoitwa ugumu-NP thabiti, strong NP-hardness), na je, mpango wa haraka unaweza kukadiria kiwango bora kwa usahihi wowote, kwa muda wa utekelezaji unaoongezeka pia kwa kiasi cha kuridhisha kadiri usahihi huo unavyoongezeka?

Uthibitisho uliopatikana pamoja na AI

Makala inaeleza jinsi ulivyopatikana. Waandishi kwanza waliiomba Codex ya OpenAI uthibitisho wa ugumu wa tatizo la jumla zaidi, kisha wakaiomba iupanue hadi misimbo isiyo ya binari (nonbinary) na mwishowe hadi misimbo ya binari. Codex ilichangia mkakati wa upunguzaji (reduction) na ukuzaji wake wa kihisabati; pia ilisaidia katika uandishi wa rasimu, ukaguzi wa hoja na ujenzi wa mifano. Waandishi waliongoza kazi, waliomba masahihisho na urahisishaji, waliandika upya maelezo kwa kiasi kikubwa, na wanabeba jukumu la kauli na uthibitisho wa mwisho. Kama chapisho lolote la awali (preprint), bado halijapitiwa na wataalamu wenzake.