KUCHAGUA NAMBA ZINAZOJUMLISHA LENGO, KARIBU KWA KASI YA KUZISOMA

Hapa kuna fumbo ambalo mtu yeyote anaweza kulieleza. Una orodha ya namba kamili — tuseme 3, 9, 14, 20 — na lengo, tuseme 23. Je, unaweza kuchagua baadhi yake ili zijumlishwe kufikia lengo hasa? (Hapa, ndiyo: 3 + 20 au 9 + 14.) Hili ni tatizo la Jumla ya Kisehemu (Subset Sum), mojawapo ya matatizo ya msingi zaidi katika sayansi ya kompyuta. Makala inalieleza kama tatizo la msingi la NP-kamili (NP-complete), familia ya matatizo yanayojulikana kuwa magumu kutatua kwa usahihi.

Hata hivyo kuna mwanya. Ikiwa namba si kubwa mno, algorithimu za werevu huendeshwa kwa muda unaotegemea ukubwa wake. Mbinu ya zamani, ya Bellman mwaka 1957, huchukua muda unaolingana na hesabu ya namba n mara lengo t. Tangu hapo, algorithimu zimeendelea kuboreshwa:

Pisinger (1999): unaolingana na n × N, ambapo N ni namba kubwa zaidi;
Bringmann (2017): takriban n + t;
timu kadhaa (2021–2024): takriban n + N^(5/3), kisha n + N^(3/2).

Kikombe kitakatifu kilikuwa muda wa takriban n + N — si zaidi sana ya kusoma ingizo. Watafiti katika fani hii walikuwa wameliita “tatizo muhimu zaidi lisilotatuliwa” la mkondo huu wa kazi.

Unywele mmoja kutoka kwenye lengo

Lin Chen, Yuchen Mao na Guochuan Zhang, wa Chuo Kikuu cha Zhejiang nchini China, wanatoa algorithimu inayoendeshwa kwa muda wa n + N^(1+ε), ambapo ε inaweza kuwa namba chanya yoyote ndogo iliyowekwa mapema — 0.1, 0.01, 0.001. Ni ya kiamuzi (deterministic), inakubali namba hasi na thamani zinazojirudia, na inakuja na uthibitisho wa kihisabati. Waandishi wanauita muda huu karibu bora kabisa (near-optimal).

Tokeo hili linapanuka hadi vekta: kuchagua vitu ili jumla kadhaa zifikie malengo yao kwa wakati mmoja, kwa muda wa N^(d+ε) kwa viwianishi d. Hilo, nalo, linajibu sehemu ya swali lililoibuliwa na vikundi kadhaa kuhusu upangaji wa namba kamili (integer programming) — kupata suluhisho za namba kamili za mifumo ya milinganyo ambayo vigeu vyake vina mipaka. Matokeo mawili yanafanyiwa kazi waziwazi: kugawanya seti ya namba kuwa nusu mbili sawa, na kugawa kazi kati ya mashine mbili zinazofanana kwa usawa kadiri iwezekanavyo.

Kuinua namba hadi kipimo cha juu zaidi

Wazo kuu ni la kijiometri. Ilikuwa tayari inajulikana kwamba tatizo ni rahisi namba zinapokuwa zimesongamana na lengo liko ndani kabisa ya wigo wa jumla zinazowezekana. Uchunguzi wa waandishi: seti ya namba zilizotawanyika inaweza kuonekana imesongamana ikitazamwa katika kipimo cha juu zaidi.

Mfano wao ni seti {11, 12, 22, 24}. Andika 11 na 22 kama hatua moja na hatua mbili kando ya mhimili wa kwanza, na 12 na 24 kama hatua moja na hatua mbili kando ya mhimili wa pili. Jumla zinazowezekana basi hujaza kila nukta ya mraba mdogo wa 4 kwa 4. Lakini ukiubana mraba huo urudi kwenye mstari — kwa kukokotoa 11x + 12y — jumla huunda vishada saba tofauti vyenye mapengo kati yake, vilivyotawanyika kati ya 0 na 69. Mapengo ni udanganyifu wa makadirio; katika vipimo viwili, muundo ni rahisi.

Algorithimu hujenga viwianishi kama hivyo vya vipimo vya juu kwa ingizo lolote, ikitumia matokeo kutoka kwenye kombinatoriki ya kujumlisha (additive combinatorics). Ndani ya eneo “lililojaa”, majibu huja bure. Ukanda mwembamba tu karibu na ukingo ndio unaohitaji kazi halisi, ambao algorithimu huugawanya kuwa matatizo madogo zaidi na kuyatatua kwa kujirudia (recursively). Kila mzunguko huupunguza ukanda huo kwa kasi, na idadi ya vipimo vipya vinavyoongezwa daima ni thabiti.

Jinsi uthibitisho ulivyojengwa

Makala inaanza na “kanusho la AI”. Waandishi walibuni wenyewe njia kuu ya uthibitisho, wakijenga juu ya kazi yao wenyewe ya karibuni kuhusu matoleo yaliyosongamana, ya vipimo vingi ya tatizo hili. Kisha walitumia modeli ya AI, GPT Astra Ultra, kugeuza mawazo haya kuwa uthibitisho kamili wa kihisabati. Ilikwama kwenye leminyo kadhaa (lemmas), ambazo zilitatuliwa kwa mawazo kutoka kwa waandishi; dokezo la utafiti la umma linarekodi mazungumzo hayo. Mara algorithimu ya msingi ya kinasibu ilipokamilika, modeli iliipanua hadi matoleo ya kiamuzi, ya vipimo vingi “bila mwongozo wowote kutoka kwa waandishi”. Modeli pia iliandaa rasimu ya makala na, waandishi wanaandika, ilihakiki matokeo yake makuu kwa uthibitisho katika msaidizi wa uthibitisho Lean 4. Waandishi wanabeba jukumu kamili la maudhui.

Si mstari wa mwisho kabisa

Kipeo ni 1 + ε badala ya 1 hasa, na visabiti vilivyofichika hukua kadiri ε inavyopungua; utegemezi wa idadi ya vipimo haujaboreshwa. Waandishi wenyewe wanaieleza algorithimu kuwa “tata kiasi”. Makala ni ya kinadharia: haiwasilishi utekelezaji wala kipimo chochote cha utendaji.