Manyta, kad išsiaiškinti, kiek mazgų yra duotame skaičiuje atkarpų susikirtimų yra neįmanomai sudėtinga. Dabar tokias užduotis gliaudo algoritminė inžinerija – ir rodo, kaip galima išspręsti kitus itin sudėtingus matematikos klausimus

Tai būdavo viena iš labiausiai nervinančių bet kokios kelionės viešuoju transportu dalių. Prasibrauni per kitų keleivių tankmę, atsisėdi ir žvejoji ausines iš kišenės. Nepasirūpinai jas tvarkingai suvynioti kai naudojai pastarąjį kartą, tad dabar tenka 5 minutes krapštytis, stengiantis išmazgyti šį gniužulą. Ačiūdie, išrastos belaidės ausinės.

Tačiau mazgai nėra vien kasdieniai nuotaikos gadintoja. Jie taip pat ir nesibaigiantis tyrėjų įkvėpimo šaltinis. Tarkime, matematiko Benjamino Burtono, kuriam ramybės neduoda vienas paprastas klausimas: kiek iš viso yra mazgų? „Tokios problemos, kurias galima paaiškinti dešimtmečiui, tačiau matematikai jos dar neišsprendė kažkuo traukia,“ sako jis.

Mazgų surašymas yra viena iš tokių problemų, kurios per sudėtingos, kad būtų įmanoma išspręsti. Gijas sukryžiuoti ir susukti galima tiek skirtingų būdų, kad visų kataloguoti negalima ir sparčiausiu kompiuteriu. Tačiau Burtono tas nesustabdė ir jis vis bandė, tuo pat metu parodydamas, kad pasitelkus kelis gudrius skaičiavimo triukus, daugelis atrodytų neišsprendžiamų matematikos tokios gali ir nebūti.

Mazgai ir mokslas susiviję jau seniai. XIX amžiaus paskutiniais dešimtmečiais mokslininkai stengėsi perprasti atomus. Pagal vieną hipotezę, jie yra skysčio verpetai, kurie tampa stabilūs kai susimazgo. Lordas Kelvinas, vėliau tapęs Londo Karališkosios draugijos prezidentu, pirmasis iškėlė mintį, kad kiekvienas cheminis elementas atitinka skirtingą mazgo tipą.

Atradus elektroną, šios idėjos atsisakyta, bet tuo metu atrodė, kad gyvybiškai svarbu suprasti mazgus. Išsamų jų sąrašą pirmasis pateikė fizikas Peter Guthrie Tait. Tiesą sakant, yra begalybė įmanomų mazgų, nes galima pridėti vis papildomų mazgų. Matematikus domina subtilesnis klausimas. Esminė mazgo savybė yra susikryžiavimų skaičius, kiek kartų gijos susikryžiuoja. O klausimas yra , kiek skirtingų mazgų galima sumegzti iš žinomo susikirtimų skaičiaus? 1885 metais Taitas, dirbdamas drauge su matematiku Thomasu Kirkmanu, nustatė visus galimus mazgus iki 10 susikirtimų imtinai. Visas nupiešęs ranka, jis suskaičiavo 364 konfigūracijas.

Toliau reikalai greitai tampa kur kas sudėtingesni. Daugėjant susikirtimų, įmanomų mazgų skaičius sparčiai didėja. Naujausias šios mazgų lentelės variantas buvo publikuotas 1998 metais. Matematikas Jim Hoste, Morwen Thistlethwaite ir Jeff Weeks sužymėjo vis mazgus iki 16 sukryžiavimų imtinai – visus 1,7 milijono.

Žengti toliau lig šiol nebuvo įmanoma. Norint suprasti priežastį, reikia pasigilinti, kaip matematikai galvoja apie mazgus (žr. „Kada mazgas nėra mazgas?“). Kitaip nei fiziniai mazgai, kurie dažniausiai būna gija laisvais galais, matematiniai mazgai yra uždari. Įsivaizduokite, užmezgėte mazgą ant gijos, o laisvus galus suklijavote.

Tempkite, sukite, lenkite

Mazgai tyrinėjami, remiantis geometrijos šakos, topologijos, taisyklėmis. Pagal jas, gijas tempiant, sukant ar lenkiant, jis išlieka fundamentaliai toks pats – bet pjaustyti ar sudaryti naujas jungtis negalima. Taip randasi pirminio mazgo sąvoka, mazgo, kurio matematiškai negalima suskaidyti į du ar daugiau paprastesnių mazgų.

Taigi, mazgų skaičiavimas susideda iš sudėtingų jungčių tikrinimo, ar jos išties yra pirminiai mazgai. Tai sudėtingesnis užsiėmimas, nei gali pasirodyti. 75 metai, du mazgai su 10 susikirtimų buvo surašyti į atskirą lentelę. Bet 1973 metais matematiką studijavęs Niujorko teisininkas, Kennethas Perko, suprato, kad paėmus veidrodinį jo atspindį, galima juo manipuliuoti taip, kad jis taptų ekvivalentus kitam. Tokie mazgai vadinami „Perko pora“.

Kartais visiškai skirtingai atrodančius mazgus galima susukti ir ištempti, kad jie būtų ekvivalentūs. Daug dešimtmečių du mazgai, vadinama Perko pora, laikyti skirtingais — kol matematikos mėgėjas neįrodė priešingai.

Kai mazgų milijonai, tokių atitikmenų paieškai reikia tiek laiko, kad net sparčiausi superkompiuteriai teoriškai negali to atlikti per protingą laiką. Tačiau 2019 metais Burtonas iš Queenslando universiteto nusprendė, kad jau metas tai išbandyti.

Jis žinojo, kad abstraktus mazgų rūšiavimo algoritmas ir jo įgyvendinimas kompiuteriniu kodu yra du skirtingi dalykai. Šio tarpo užpildymo menas vadinamas algoritmų inžinerija ir Burtonas manė, kad pasitelkus tinkamus triukus, ši problema nebus tokia sudėtinga, kaip atrodo. „Iš dalies mane motyvas buvo sukurti demonstracinį stendą, kuriame būtų matoma, ar turimi įrankiai pakankamai geri,“ paaiškina jis.

Jis pradėjo, nurodydamas kompiuteriui užduotį sugalvoti visus įmanomus būdus, kiek būdų gijos galėtų būti sumegztos, kai susikirtimų yra iki 19 imtinai. Tai ganėtinai paprasta užduotis ir vos po kelių dienų kompiuteris pateikė 21 milijardą kandidatų.

Tuomet reikėjo patikrinti kiekvieną mazgą, ar jis pirminis ir išskirtinis. Tam reikia visus topologinius mazgų aprašus įkelti į kompiuterio darbinę atmintį, RAM. 21 milijardo mazgų aprašymo duomenims reikėtų daugiau, nei 1 terabaito RAM, ir tiek atminties turintys kompiuteriai nėra dažni. Burtonas šią kliūtį apėjo, pasinaudodamas savo sukurtos programinės įrangos paketu Regina. Juo mazgai konvertuojami į „mazgų parašus“, raidžių sekas, kuriomis aprašomos kiekvieno mazgo būdingos topologinės savybės. Parašai užima daug mažiau vietos, nei mazgų aprašai. Be to, skirtingai sumazgytų, bet iš tiesų ekvivalenčių mazgų parašai vienodi, tad lengva išravėti duplikatus. Burtonui pavyko patikrinti po maždaug 7 milijardus kandidatų per dieną.

Tačiau šis metodas nebuvo pakankamai galingas, kad galėtų identifikuoti visus iki vieno duplikatus. Toliau Burtonas suskaičiavo kiekvieno kandidato mazgo invariantiškumą. Invariantai yra matematiniai objektai, perteikiantys mazgo esmę – jei dviejų mazgų invariantai skiriasi, tai skiriasi ir patys mazgai. Invariantai yra galingesni įrankiai už parašus, bet ir suskaičiuoti juos sunkiau: Burtono kompiuteris likusių mazgų invariantus būtų skaičiavęs ilgiau, nei metus. Surūšiavęs juos į grupes ir pasinaudodamas paraleliais superkompiuteriais, visus juos apdorojo per kelias dienas. Rinkinys susitraukė iki 370 milijonų.

Burtonui dar teko vargti su itin reiklia kategorija – nehiperboliniais mazgais. Bet po dar kelių rūšiavimų tariamai neįmanoma užduotis buvo įveikta. Burtono sąrašas mazgų lentelę išplėtė iki 19 susikirtimų imtinai. Galutinis rezultatas: 352 152 252 mazgų.

Ian Agol iš Kalifornijos universiteto Berkeleyje sako, kad skaičiavimai jam paliko įspūdį. „Tai tikriausiai padės matematikams ieškoti konkrečių savybių mazgų, ar norintiems identifikuoti dominantį mazgą,“ sako jis.

Jis ir kiti matematikai mano, kad Burtono darbas – įspūdingas algoritmų inžinerijos pavyzdys. „Tai kylanti tendencija fundamentaliojoje matematikoje, kur skaičiavimo metodai naudojami kūribiškiau,“ pastebi Hans Boden iš McMaster universiteto Ontarijuje, Kanadoje.

Keltai ir kameros

Yra daug praktiškų problemų, kur algoritmų inžinerija naudojama ieškoti efektyvių sudėtingų problemų sprendimų. Vienos iš svarbiausių kyla logistikoje, kur gabenimo optimizavimas taupo laiką ir pinigus. Kitas pavyzdys – stebėjimo kamerų išdėstymas. Daugeliu atvejų idealaus sprendimo per apibrėžtą laiko tarpą pasiekti neįmanoma.

Dar tai tinka ir aiškinantis sudėtingas evoliucijos istorijas, ypač augalų ir bakterijų. Algoritmais DNR duomenys susiejami į filogenetinius medžius, grafas, arčiau giminingas rūšis grupuojant ariau, nei mažiau giminingas. Tačiau kartais genai nepereina iš tėvų atžaloms, o vadinamuoju horizontaliu genų pernešimu iš vienos rūšies kitai. Tokius perkėlimus fiksuoti sukurti algoritmai gali būti labai lėti.

Vienas algoritmų inžinerijos triukas, padedantis to išvengti, yra gaunamų duomenų parametrizavimas, taip juos sumažinant. Pavyzdžiui, fiksavus dominančių potencialių mutacijų skaičių, problema gali būti efektyviai išsprendžiama. Neseniai, Edwin Jacox, dabar dirbantis Kalifornijos universitete, Santa Cruz, su kolegomis pritaikė šį metodą cianobakterijų filogenetiniams medžiams. Cianobakterijos suvaidino svarbiausią vaidmenį Žemės biosferos pasikeitime prieš daugiau nei 2 milijardus metų. Tyrėjai sukūrė parametrizuotą algoritmą, kuris cianobakterijų filogenetinį medį atkūrė vos per 15 sekundžių.

Ar rekonstruojant evoliucijos medžius, ar skaičiuojant mazgus, aišku, kad sudėtingiausias skaičiavimo problemas galima padaryti išsprendžiamas. „pasinaudojant algoritmų inžinerija ir euristika, dalykai, kurie praktikoje lėti, tampa išskirtinai, stulbinamai greiti,“ sako Burtonas. Tai reiškia, kad net kebliausios problemos nebūtinai yra neišsprendžiamos.

Kada mazgas nėra mazgas?

Štai kokią problemą reikia išspręsti: jei patempi giją susipainiojusių laidų gniutule, kaip žinoti ar taip jis labiau susipainios ar suirs į paprastesnę kilpą? Tokias problemas matematikai vadina „išpainiojimo atpažinimu“ ir vieną galime netrukus išspręsti. Išpainiojimo atpažinimas žavi ir matematikus, ir kompiuterių mokslininkus, jie yra garsiojo „P vs NP“ klausimas.

Kad pamatytumėme kaip tai veikia, panagrinėkime klasikinę keliaujančio pirklio problemą, kur reikia išsiaiškinti trumpiausią kelią, kuriuo pirklys aplankytų miestus. Jei šios problemos sprendimo algoritmas netampa eksponentiškai sunkesnis, daugėjant miestų skaičiui, jis yra „P“. Tai reiškia, kad jis išsprendžiamas per protingą – arba matematikų kalba šnekant, polinominį – laiką. Gavus atsakymą, reikia patikrinti, ar jis teisingas. Jei atsakymą patikrinti lengva, tuomet problema klasifikuojama kaip „NP“. Didysis matematikų klausimas yra ar visos NP problemos yra ir P. Tai viena iš tūkstantmečio premijos problemų – atsakykite į šį klausimą pagrįstai ir laimėsite 1000 000＄.

Išmazgymo pripažinimas slypi P vs NP prietemos zonoje. Jau žinome, kad ši problema yra užtikrintai „NP“, tai yra, lengvai patikrinama. Jeigu jūsų algoritmas gali sukurti nesumazgytą kilpą, tai matosi iš karto. Matematikai mano, kad ši problema tikriausiai yra ir P, ir nedaug trūksta tai įrodyti.

2014 metais Benjaminas Burtonas iš Queenslando universitete Australijoje sukūrė išmazgymo algoritmą, kuris problemą praktiškai sprendžia per polinominį laiką. Jo algoritmas susidorojo „su bet kokiais mazgais, kokius tik ligšiol pateikėme“, sako jis. Vėliau, Marc Lackenby iš Oxfordo universiteto sukūrė išmazgymo atpažinimo logaritmą, kuris yra „quasi-P“ (matematikų žargonu tai reiškia „beveik tinkamas“). Vargu ar jis bus paverstas kompiuteriniu kodu, nes yra labai sudėtingas, bet Lackenby neabejoja, kad supaprastinta versija „bus išties praktiška“.

Pademonstravimas, kad išmazgymo atpažinimas yra P ir NP, Tūkstantmečio prizo problemos neišspręs, nors gali suteikti naudingų nuorodų. Tačiau tai svarbus pasiekimas ir matematikai švęs, kai tai bus pasiekta.

Komentarai ()