ZAƁAR LAMBOBIN DA SUKA HAƊU, KUSAN DA SAURIN KARANTA SU

Ga wani wasan wasa da kowa zai iya faɗa. Kana da jerin lambobi cikakku — misali 3, 9, 14, 20 — da manufa, misali 23. Za ka iya zaɓar wasu daga cikinsu don su haɗu daidai zuwa manufar? (A nan, i: 3 + 20 ko 9 + 14.) Wannan ita ce Subset Sum, ɗaya daga cikin matsaloli mafi tushe a kimiyyar kwamfuta. Takardar ta bayyana ta a matsayin matsala ta tushe ta NP-complete, iyalin matsaloli da aka san su da wuyar warwarewa daidai.

Akwai wata kafa, duk da haka. Idan lambobin ba su yi girma sosai ba, algorithms masu wayo suna gudana a lokaci da ya dogara ga girmansu. Hanyar gargajiya, ta Bellman a 1957, tana ɗaukar lokaci daidai gwargwado da yawan lambobi n sau manufa t. Tun daga lokacin, algorithms sun ci gaba da ingantuwa:

• Pisinger (1999): daidai gwargwado da n × N, inda N ita ce lamba mafi girma;
• Bringmann (2017): kusan n + t;
• ƙungiyoyi da dama (2021–2024): kusan n + N^(5/3), sannan n + N^(3/2).

Babban buri shi ne lokaci kusan n + N — ba fiye da karanta shigarwar sosai ba. Masu bincike a fannin sun kira shi “matsala mafi muhimmanci da ba a warware ba” a wannan layin aiki.

Kusa da manufa sosai

Lin Chen, Yuchen Mao da Guochuan Zhang, na Jami’ar Zhejiang a China, sun ba da algorithm da ke gudana a lokaci n + N^(1+ε), inda ε zai iya zama kowace ƙaramar lamba mai kyau da aka kafa tun farko — 0.1, 0.01, 0.001. Tana da tabbaci (deterministic), tana karɓar lambobi korarru (negative) da ƙimomi masu maimaituwa, kuma tana zuwa da hujjar lissafi. Marubutan sun kira wannan lokaci near-optimal (kusan mafi kyau).

Sakamakon ya faɗaɗa zuwa vectors: zaɓar abubuwa ta yadda jimloli da dama za su kai manufofinsu lokaci guda, da lokaci N^(d+ε) ga coordinates d. Wannan kuma yana amsa wani ɓangare na tambayar da ƙungiyoyi da dama suka yi game da integer programming — samun mafita na lambobi cikakku ga tsarin daidaito waɗanda canje-canjensu ke da iyaka. An fitar da sakamako biyu a fili: raba saitin lambobi zuwa rabi biyu masu daidaito, da raba ayyuka tsakanin injuna biyu iri ɗaya daidai-wa-daida gwargwadon iko.

Ɗaga lambobi zuwa girma mafi girma

Babban ra’ayin na lissafin siffofi (geometry) ne. An riga an san cewa matsalar mai sauƙi ce idan lambobin suna cunkushe (dense) kuma manufar tana cikin kewayon jimlolin da za su yiwu sosai. Lura da marubutan: saitin lambobi masu warwatsuwa (sparse) zai iya yin kama da cunkushe idan aka kalle shi a cikin girma mafi girma.

Misalinsu shi ne saitin {11, 12, 22, 24}. Rubuta 11 da 22 a matsayin mataki ɗaya da matakai biyu a kan axis na farko, da 12 da 24 a matsayin mataki ɗaya da matakai biyu a kan axis na biyu. Jimlolin da za su yiwu sai su cika kowane wuri na ƙaramin murabba’i na 4 da 4. Amma idan aka matse wannan murabba’i baya zuwa layi — ta hanyar lissafa 11x + 12y — jimlolin suna samar da gungu bakwai daban-daban da giɓi a tsakaninsu, a warwatse tsakanin 0 da 69. Giɓin ruɗi ne na projection; a girma biyu, tsarin mai sauƙi ne.

Algorithm ɗin tana gina irin waɗannan coordinates na girma mafi girma ga kowace shigarwa, ta amfani da sakamakon additive combinatorics. A cikin yankin da ya “cika”, amsoshi suna zuwa kyauta. Siririn yanki kusa da gefe ne kaɗai ke buƙatar aiki na gaske, wanda algorithm ɗin ke rarrabawa zuwa ƙananan matsaloli kuma ta warware su recursively. Kowane zagaye yana rage wannan yanki da ƙarfi, kuma adadi kafaffe ne kawai na sababbin girma ake ƙarawa.

Yadda aka gina hujjar

Takardar ta fara da “AI disclaimer”. Marubutan sun tsara babbar hanyar hujjar da kansu, suna ginawa a kan aikinsu na baya-bayan nan kan sigogin matsalar masu cunkushe, masu girma da dama. Sannan suka yi amfani da wata ƙirar AI, GPT Astra Ultra, don mayar da waɗannan ra’ayoyi zuwa cikakkun hujjojin lissafi. Ta makale a kan lemmas da dama, waɗanda aka warware da ra’ayoyi daga marubutan; wata takardar bincike ta jama’a ta rubuta tattaunawar. Da zarar an gama asalin algorithm ta bazata (randomised), ƙirar ta faɗaɗa ta zuwa sigogin masu tabbaci, masu girma da dama “ba tare da wata jagora daga marubutan ba”. Ƙirar ta kuma rubuta daftarin takardar kuma, marubutan sun rubuta, ta tabbatar da manyan sakamakonta da hujja a cikin mataimakin hujja Lean 4. Marubutan sun ɗauki cikakken alhakin abin da ke ciki.

Ba ƙarshen layi ba tukuna

Exponent ɗin shi ne 1 + ε maimakon 1 daidai, kuma ɓoyayyun constants suna girma yayin da ε ke raguwa; ba a inganta dogaro kan yawan girma ba. Marubutan da kansu sun bayyana algorithm ɗin a matsayin “mai sarƙaƙiya sosai”. Takardar ta ka’ida ce: ba ta bayar da rahoton wani aiwatarwa ko benchmark ba.