Vilniaus universiteto Matematikos ir informatikos instituto profesorius Leonidas Sakalauskas DELFI sutiko papasakoti apie vieną jų.
„PvsNP“ problema laikoma viena svarbiausių kompiuterių moksle, tačiau iš pirmo žvilgsnio ji atrodo kaip nesudėtingas galvosūkis. Šią problemą gali suprasti ir pradinukai“, – įsitikinęs jis.
Anot L. Sakalausko, problemos esmė – paprasta: „Duota daiktų krūvelė. Kaip ją padalinti į kuo mažiau besiskiriančias krūveles?“
Problemos neišsprendžia jau 59 metus
„Informatika yra mokslas apie skaičiavimus, nors šis dalykas dažnai tapatinamas su kompiuterių mokslu (Computer Science). Informatika tyrinėja algoritmų struktūrą, elgesį bei sąveiką, čia algoritmu vadinamas taisyklių rinkinys, skirtas kokiam nors uždaviniui spręsti.
„P versus NP“ problema yra laikoma svarbiausia informatikos problema. Ji pirmąkart buvo paminėta 1956 m. žymaus vokiečių logiko Kurto Giodelio laiške vienam iš šiuolaikinių kompiuterių kūrėjų Džonui fon Neimanui, o matematiškai griežtai suformuluota amerikiečių mokslininko Stefeno Kuko 1971 m. Ši problema laikoma viena svarbiausių informatikos ir matematikos problemų ir yra įtraukta į Tūkstantmečio prizo („Millenium Prize“) problemų sąrašą, o pirmasis ją išsprendęs būtų apdovanotas 1000 000 JAV dolerių (893 256 eur.) prizu.
„PvsNP“ problema nagrinėja iš pirmo žvilgsnio paprastus uždavinius, gana dažnai pasitaikančius gyvenime, tačiau šių uždavinių sprendimas gali būti labai sunkus ir pareikalauti daug sprendėjų pastangų ir kompiuterio išteklių, tarp kurių svarbiausi yra kompiuterio laikas ir atmintis“, – pasakojo profesorius.
Panašias problemas moksleiviai „kremta“ per pamokas
Jis pateikė pavyzdį. Tarkime, verslo sėkmė labai priklauso nuo to, kaip tiekiamos ir skirstomos medžiagos bei žaliavos, apkraunami įrengimai ar priskiriamos užduotys personalui ir pan.
„Paprastumo dėlei, tarkime, kad dviem procesoriams (arba kitokiems įrenginiams) reikia paskirstyti tam tikrus darbus, kurių trukmės yra žinomos iš anksto. Tegul tos trukmės (sekundėmis) sudaro seką RIGHT_BRACKET13, 11, 5, 5, 9, 8LEFT_BRACKET. Šiek tiek pasukus galvą nesunku pamatyti, kad geriausia pirmajam procesoriui priskirti darbus su trukmėmis RIGHT_BRACKET13,5,8LEFT_BRACKET, o kitus darbus atlikti su antruoju procesoriumi. Tuomet darbai bus atlikti po 26 sek. Kitoks darbų tvarkaraštis gali tik sulėtinti darbų atlikimo pabaigą.
Aišku, kad geriausią darbų priskyrimo dviem procesoriams tvarkaraštį galima surasti apskaičiavus ir palyginus visus įmanomus tvarkaraščius, kurių skaičius lygus skirtingų darbų derinių skaičiui.
Nesunku pastebėti, jog dviejų darbų atveju tokių derinių būtų 4, trijų – 8, o bendru atveju visų skirtingų tvarkaraščių skaičius išreiškiamas rodykline priklausomybe - 2n, čia n yra darbų skaičius.
Ši iš pirmo žvilgsnio paprasta priklausomybė, ją moksleiviai „kremta“ per matematikos pamokas mokykloje, pasižymi klastingomis savybėmis, būtent, nedaug pakitus laipsnio rodikliui n, uždavinio sprendimas žymiai pasunkėja (pavyzdžiui, prie 1000 darbų pridėjus tik vieną, optimalaus dviejų procesorių tvarkaraščio radimas perrinkimo būdu pailgėja tiek, kiek reikia laiko visam 1000 darbų uždaviniui išspręsti).
Be to, ji pasižymi „sprogimo“ efektu, nes esamų išteklių riba, reikalinga uždaviniui spręsti, pasiekiama gana greit (pavyzdžiui, kai n~30, dviejų procesorių tvarkaraščio uždavinius dar galima spręsti su asmeniniu kompiuteriu, tačiau gali pasitaikyti uždavinių su n~100, kurių neišspręstų visi mūsų planetos kompiuteriai dirbdami tiek laiko, kiek praėjo nuo Visatos atsiradimo per Didįjį Sprogimą)“, – pastebėjo L. Sakalauskas
Keli uždaviniai vienu sprendimu
„Natūraliai kyla klausimas, ar galima iš esmės sumažinti visų nagrinėjamų variantų skaičių? Juoba, dar 1972 m. amerikietis Ričardas Karpas pastebėjo, jog įvairių, iš pirmo žvilgsnio skirtingų uždavinių sprendimai gali būti suvedami vienas į kitą. Todėl visus žinomus sunkiai sprendžiamus uždavinius galima suskirstyti į panašių uždavinių klases, kur išsprendus kurį nors vienos klasės uždavinį, paaiškėtų, kaip spręsti ir kitus tos klasės uždavinius, o tiriant gana sudėtingas problemas, pakaktų išnagrinėti tik paprastesnius, būdingus tos klasės uždavinius, kurių sprendimas duotų raktą sudėtingesniems uždaviniams spręsti.
Pavyzdžiui, mokant greitai spręsti dviejų tvarkaraščių uždavinį, galima taip pat efektyviai sudarinėti sudėtingesnius tvarkaraščius, patobulinti atsiskaitymus tarp bankų (bankai ir kai kurios kitos finansų institucijos kelis kartus per dieną atlieka tarpusavio pavedimų užskaitymus, kurių atlikimas bendru atveju yra sunkus uždavinys), efektyviai planuoti sandėliavimo ir pervežimo darbus (automatizuotos konteinerių krovos ir pervežimų optimizavimas taip pat yra sunkiai sprendžiamas uždavinys), ir pan.“, – sakė profesorius.
Anot jo, apibūdinant sunkiai sprendžiamus uždavinius, pagrindinis rodiklis yra duomenų, reikalingų uždavinio sąlygai užrašyti, apimtis.
„Pavyzdžiui, banko kodo atveju tokiu rodikliu yra kodo skaitmenų skaičius, kituose dviejuose pavyzdžiuose sąlygos uždavinio sudėtingumo rodikliu yra skaičių aibės elementų skaičius n“, – patikslino L. Sakalauskas.
Ištyrė daugiau nei 3 tūkst. panašių uždavinių, bet ne šį
„Sąvoka „greitai“, paminėta aukščiau, reiškia, kad egzistuoja algoritmas, leidžiantis išspręsti uždavinį per trumpesnį iš esmės laiką, nei pilnas visų variantų perrinkimas. Kadangi kita paprasta, žinoma dar iš mokyklos laikų, priklausomybė – laipsninė, kuri visada auga lėčiau negu rodyklinė, tyrėjai labai stengiasi atrasti tokius algoritmus, kurių sprendimo laikas kistų bent laipsniškai priklausomai nuo uždavinio sąlygos sudėtingumo. Bendru atveju tokia priklausomybė būtų išreiškiama daugianariu, nes į ją gali įeiti ir kiti n laipsniai.
Kadangi daugianariams yra prigijęs tarptautinis polinomų pavadinimas, algoritmai, kurių sudėtingumas kinta laipsniškai arba, bent, išreiškiamas daugianariu, yra vadinami polinominio sudėtingumo. Taigi, sprendžiant „PvsNP“ problemą, reikia atsakyti į klausimą, ar įmanoma rasti algoritmą, kuris leistų NP klasės uždavinius, paprastai sprendžiamus perrinkus visus galimus variantus, išspręsti per polinomiškai sudėtingą laiką ? Jau minėjau, tam pakaktų surasti greitą būdą spręsti nors vienos klasės uždavinius, pavyzdžiui, dviejų tvarkaraščių, kurių pavyzdį pateikiau aukščiau.
Reikia pažymėti, jog per laiką, praėjusį nuo šios problemos paskelbimo, buvo ištirta daugiau nei 3000 sunkių NP klasės uždavinių, kurių polinominio sudėtingumo sprendimo dar nepavyko rasti. Vienoks ar kitos PvsNP problemos sprendimas būtų labai svarbus informatikai, matematikai, kriptografijai, dirbtinio intelekto mokslui, filosofijai, ekonomikai ir kt.“, – sakė jis.
Sprendimas reikštų milžinišką šuolį
„Jei pasirodytų, kad P = NP, t.y., visus sunkius NP klasių uždavinius galima išspręsti polinominio sudėtingumo algoritmais, tai reikštų perversmą, kurį būtų galima palyginti su valdomos termobranduolinės reakcijos atradimu. Toks „PvsNP“ problemos sprendimas reikštų perversmą matematikoje, sprendžiant daugelį iki šiol neišspręstų matematinių problemų, kurias būtų galima tuomet spręsti kompiuteriais, nors tų uždavinių sprendimas tradiciniais metodais pareikalaudavo didelių daugelio tyrėjų pastangų.
Pavyzdžiui, kompiuteriu būtų galima išspręsti visas Tūkstantmečio prizo problemas. Įrodymas, jog P = NP turėtų milžinišką praktinę reikšmę, ypač, jei šis įrodymas leistų sukurti efektyvius metodus svarbioms NP problemoms spręsti. Tai leistų efektyviai spręsti daugelį planavimo, atsiskaitymų ir kitokių logistikos uždavinių, nulemtų reikšmingą proveržį, šuolį bioinžinerijoje, tiriant baltymų struktūras, ir be abejo, tektų peržiūrėti daugelį kriptografijos sprendimų kompiuterių saugumo sistemose.
Jei P ≠ NP, tai reikštų, kad yra tokių uždavinių, kuriuos daug sunkiau išspręsti, negu patikrinti. Įrodymas P ≠ NP neturėtų tokių praktinių privalumų, kaip P = NP, tačiau tai būtų svarbus žingsnis skaičiavimų sudėtingumo teorijoje ir padėtų geriau suprasti, kurie uždaviniai galėtų būti sprendžiami efektyviau“, – pastebėjo profesorius.
Ką mano tyrėjai?
„Dauguma tyrėjų mano, kad P ≠ NP. Ši nuomonė remiasi tuo, jog per keliasdešimt metų nepavyko pasistūmėti į priekį, sprendžiant daugiau kaip 3000 aktualių NP uždavinių. 2002 m. apklausus 100 tyrėjų, 61 iš jų tikėjo, kad P ir NP klasės nesutampa, 9 manė, kad galima sukurti polinominį algoritmą sudėtingiems uždaviniams spręsti, 22 nežinojo, ką atsakyti, o 8 manė, kad problemos neįmanoma įrodyti ar paneigti, naudojantis šiuo metu priimtomis aksiomomis. Pakartojus apklausą po 10 metų, apklaustųjų pasiskirstymas bemaž nepasikeitė.
Bandant rasti efektyvius algoritmus sunkiai sprendžiamiems uždaviniams spręsti, tyrėjų dėmesys nukrypo į apytikrių tokių uždavinių sprendimo metodus. Iš tikrųjų praktikoje pakanka rasti sprendimą, kuris nebūtų geriausias, bet jam nors artimas. Kadangi P ≠ NP problema kol kas palieka atvirą klausimą apie vidutinišką sunkių NP uždavinių sudėtingumą, siekiama sukurti algoritmus, kurie leistų spręsti daugelį praktiškai pasitaikančių uždavinių per vidutiniškai priimtiną laiką, tikintis, jog atskiri sunkūs atvejai, kurių sprendimas paaiškėja tik po pilno perrinkimo, pasitaikys gana retai.
Tokie metodai dažnai kuriami ieškant analogijų gyvojoje gamtoje, ir yra priskiriami dirbtinio intelekto sričiai. Einant šiuo keliu, kuriami euristiniai algoritmai, modeliuojantys smegenų neuronų darbą, vabzdžių populiacijų elgesį (skruzdžių ar bičių algoritmai) ir pan. Nors šie algoritmai neužtikrina optimalaus sprendinio radimo, jie padeda rasti sprendinį, artimą optimaliam. Tačiau IT įmonės Lietuvoje, užsiimančios logistika, tiekimu, planavimu ir pan., šių algoritmų beveik dar nežino, tad euristinių bei kitų dirbtinio intelekto algoritmų praktinis panaudojimas yra aktuali verslo konkurencingumo ir efektyvumo plėtotės kryptis“, – sakė L. Sakalauskas.
Pasak profesoriaus, „PvsNP“ problemai didelis dėmesys skiriamas ne tik visame pasaulyje, bet ir Lietuvoje. Prie jo dirba nemažai tyrėjų. Pavyzdžiui, VU Matematikos ir informatikos instituto (MII) mokslininkas Stasys Jukna, dirbantis Vokietijoje.
„Jis ištyrė daugelį plačiai taikomų algoritmų klasių, ir parodė, kad polinominio algoritmo tose klasėse nėra. VU MII ginamose disertacijose taip pat dažnai gvildenamos sunkių uždavinių sprendimo klasikinių bei euristinių algoritmų savybės“, – patikino L. Sakalauskas.