Kompyuta na akili bandiaChapisho la awaliNadhariaDakika 4 za kusoma

KISABITI CHA 10⁴⁰ CHASHUSHWA HADI 30.5 KWA MICHEMRABA MIKUBWA MNO YA RUBIK

Mchemraba wa Rubik (Rubik’s Cube), ambao umetimiza miaka 50 hivi karibuni, huenda ndilo fumbo linalojulikana zaidi duniani, na mojawapo ya maswali yake makuu ni rahisi kueleza: katika hali mbaya zaidi, inahitaji miendo mingapi kuutatua? Kwa mchemraba wa kawaida wa 3×3×3, jibu linajulikana kwa usahihi: miendo 20, matokeo yaliyochapishwa mwaka 2014 na timu iliyojumuisha Tomas Rokicki, mmoja wa waandishi wa makala hii mpya.

Kwa michemraba mikubwa zaidi, yenye tabaka n kando ya kila ukingo, jibu kamili haliwezi kufikiwa — kutatua mchemraba fulani wa n×n×n kwa njia bora kabisa ni hata tatizo NP-complete. Lakini mwaka 2011, Erik Demaine na wenzake walionyesha jinsi hali mbaya zaidi inavyokua: kwa uwiano wa n² / lg n, ambapo lg ni logariti ya msingi 2. Hiyo ni bora kwa kigawo cha kilogariti kuliko mbinu za kawaida, ambazo kimsingi hutatua vipande kimoja baada ya kingine.

Uthibitisho wenye kisabiti kisicho na mantiki

Kulikuwa na tatizo. Matokeo ya 2011 yalihakikisha kasi ya ukuaji, si namba iliyo mbele yake. Wakipitia algoriti hiyo hatua kwa hatua, waandishi wanagundua kwamba kisabiti chake ni takriban 1.01 × 10⁴⁰. Chanzo cha tatizo ni ukaguzi wa kompyuta uliothibitisha kwamba miendo fulani inaweza kufikia kila mpangilio wa kikundi cha vipande 24, bila kusema ni kwa haraka kiasi gani. Kikomo pekee salama cha urefu huo kilikuwa ukubwa wa kundi hilo la mipangilio, takriban hatua 3.1 × 10²³, na fomula inaishia kutumia namba kubwa mno 24! (1 × 2 × … × 24, takriban 6.2 × 10²³) mahali pawili. Kwa upande mwingine, kikomo cha chini — idadi ya miendo ambayo karibu kila mchemraba uliovurugwa unahitaji — kina kisabiti cha kiasi cha takriban 12.88. Kwa hiyo wengi katika jumuiya hii waliamini kwamba algoriti kama hiyo isingeweza kamwe kutumika kivitendo kwa ukubwa unaoeleweka.

Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf na Erik Demaine, kutoka MIT, TU Munich na Palo Alto, sasa wamekifanya kisabiti hicho kuwa wazi na kidogo.

Mitandao ya kupanga kwa vipande vya mchemraba

Kwenye mchemraba mkubwa, vipande vya katikati ndivyo vinavyotawala: idadi yake hukua kama n², ilhali pembe na kingo huongeza tu vipengele vinavyolingana na n. Vipande vya katikati hugawanyika katika familia za vipande 24 ambavyo vinaweza kubadilishana nafasi miongoni mwao tu. Chombo cha msingi ni kibadilishi (commutator), mfuatano wa umbo A B A′ B′ unaoacha karibu kila kitu mahali pake na kubadilisha nafasi za vipande vitatu tu vya familia moja. Timu ilipata mifuatano ya miendo kwa ubadilishanaji wote 4,000 unaoweza kutumika wa vipande vitatu, kila mmoja ukiwa na urefu usiozidi miendo 12.

Mawazo mawili yanafanya idadi hiyo ishuke. Kwanza, kibadilishi kilekile kinaweza kutumika kwa familia nyingi kwa wakati mmoja, katika makundi mazima ya safu mlalo na safu wima. Pili, badala ya kutatua kila familia peke yake, kila familia hufuata mfuatano mmoja wa jumla (universal sequence) usiobadilika wa ubadilishanaji, ikiruka tu ubadilishanaji usiouhitaji. Lema (lemma) moja inaunganisha kila kitu: mfuatano wa jumla wenye hatua L hutoa kisabiti kikuu cha L/2.

Kufupisha mfuatano huo kunaazima zana kutoka kwa mitandao ya kupanga (sorting networks) ya sayansi ya kompyuta, mipangilio isiyobadilika ya ulinganishaji inayopanga ingizo lolote. Mtandao bora wa kupanga wenye maingizo sita unatoa hatua 96, hivyo kisabiti cha 48. Mitandao inayogawa nafasi 24 katika makundi ya 12, kisha ya 4, iliyopatikana kwa utafutaji wa kompyuta, inaishusha hadi hatua 72 (36). Mwishowe, kuruhusu miendo inayochanganya zaidi ya vipande vitatu kwa wakati mmoja na kugawa nafasi kwa njia tofauti kunaishusha hadi hatua 61.

Thelathini nukta tano

Nadharia (theorem) inasema: mchemraba wowote wa n×n×n unaweza kutatuliwa kwa miendo isiyozidi 30.5 n²/lg n, pamoja na vipengele ambavyo vinakuwa vidogo kiasi cha kupuuzwa kwa n kubwa. Kisabiti kinaboreka kwa zaidi ya mara 3.30 × 10³⁸, na hakizidi mara 2.37 ya kikomo cha chini (30.5 / 12.88). Kwa toleo bapa la n×n×1, linalotumiwa kama zoezi la kujipasha moto, kisabiti kinashuka kutoka 12 au 18 hadi 1.5.

Fremu nane za mchemraba wenye tabaka 256 ukitatuliwa, zikionyeshwa kama nyuso zilizokunjuliwa na kama michemraba midogo, kutoka mchanganyiko wa rangi uliovurugika hadi rangi zisizochanganyika.

Fremu nane zilizo na nafasi sawa kati yake za utatuzi wa mchemraba wenye tabaka 256 kila upande: nyuso zilizovurugwa zinageuka kuwa rangi zisizochanganyika. — Kielelezo 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.

Algoriti hiyo inachukua muda unaolingana na idadi ya vipande, na waandishi wanatoa programu huria ya kutatua, pamoja na hati (scripts) zinazokagua kikamilifu kila mtandao inaoutegemea. Ulinganisho wao wenyewe unaonyesha kwamba inazishinda programu zilizopo za kutatua kuanzia takriban n = 840; wametengeneza michoro ya utatuzi wa michemraba yenye tabaka 256 na 65,536 kila upande.

Ile 2.37 ni kauli ya kiasimptotiki (asymptotic): vipengele vidogo zaidi vya fomula havijabainishwa kwa usahihi, kwa hiyo haitoi idadi kamili kwa mchemraba fulani. Maboresho ya baadaye, waandishi wanapendekeza, yanaweza kutoka kwa njia nyingine za kupanga vipande katika makundi ya mitandao ya kupanga na kutoka kwa ubadilishanaji bora zaidi wa vipande vitatu — na zana hizohizo zinaweza kushughulikia mafumbo mengine makubwa mno, au michemraba-kuu (hypercubes) ya vipimo vinne na vitano.