admin
Originali versija iš Ši istorija Pasirodė žurnale „Quanta“.
Pateikite klausimą „Magic 8“ rutuliui, ir jis atsakys taip, ne, ar kažkas erzinančiai neryžtingo. Mes galvojame apie tai kaip apie vaiko žaislą, tačiau teoriniai kompiuterių mokslininkai naudoja panašų įrankį. Jie dažnai įsivaizduoja, kad gali pasikonsultuoti su hipotetiniais įrenginiais, vadinamais „Oracles“, kurie gali akimirksniu ir teisingai atsakyti į konkrečius klausimus. Šie išgalvotos minties eksperimentai įkvėpė naujus algoritmus ir padėjo tyrėjams susieti skaičiavimo kraštovaizdį.
Tyrėjai, kurie kreipiasi į „Oracles“, dirba informatikos polaukyje, vadinamame skaičiavimo sudėtingumo teorija. Jiems rūpi būdingi problemų, tokių kaip nustatymas, ar skaičius yra pagrindinis, ar suranda trumpiausią kelią tarp dviejų tinklo taškų. Kai kurias problemas lengva išspręsti, kiti atrodo daug sunkesni, tačiau turi sprendimus, kuriuos lengva patikrinti, o kitiems – lengva kvantiniams kompiuteriams, tačiau, atrodo, sunku paprastiems.
Sudėtingumo teoretikai nori suprasti, ar šie akivaizdūs sunkumų skirtumai yra esminiai. Ar yra kažkas iš esmės sunku dėl tam tikrų problemų, ar mes tiesiog nesame pakankamai protingi, kad sugalvotume gerą sprendimą? Tyrėjai išsprendžia tokius klausimus, rūšiuodami problemas į „sudėtingumo klases“-visos lengvos problemos kyla, pavyzdžiui, vienoje klasėje, o visos lengvai painiojamos problemos kyla kitoje-ir įrodo teoremas apie tų klasių ryšius.
Deja, skaičiavimo sunkumų kraštovaizdžio žemėlapis pasirodė sunkus. Taigi aštuntojo dešimtmečio viduryje kai kurie tyrėjai pradėjo tyrinėti, kas nutiktų, jei skaičiavimo taisyklės būtų kitokios. Štai kur ateina orakulai.
Kaip ir „Magic 8“ rutuliai, „Oracles“ yra įrenginiai, kurie iškart atsako į klausimus „taip“ arba „ne“, nieko neatskleidžiant apie savo vidinį darbą. Skirtingai nuo „Magic 8“ kamuolių, jie visada sako „taip“ arba „ne“ ir visada yra teisingi – pranašumas yra išgalvotas. Be to, bet kuris nurodytas „Oracle“ atsakys tik į tam tikrą klausimų tipą, pavyzdžiui, „Ar šis skaičius yra promenduojamas?“
Kas daro šiuos išgalvotus prietaisus naudingus norint suprasti realų pasaulį? Trumpai tariant, jie gali atskleisti paslėptus ryšius tarp skirtingų sudėtingumo klasių.
Vykdykite dvi garsiausias sudėtingumo klases. Čia yra lengva išspręsti problemas, kurias tyrėjai vadina „P“ ir problemų, kurias lengva patikrinti, klasę, kurią tyrėjai vadina „NP“. Ar visas lengva išspręsti problemas taip pat lengva išspręsti? Jei taip, tai reikštų, kad NP būtų lygus P, o visą šifravimą būtų lengva nulaužti (be kitų pasekmių). Sudėtingumo teoretikai įtaria, kad NP neprilygsta P, tačiau jie negali to įrodyti, nors jie bandė užmegzti santykius tarp dviejų klasių daugiau nei 50 metų.
„Oracles“ padėjo jiems geriau suprasti, su kuo jie dirba. Tyrėjai išrado orakules, atsakiusi į klausimus, kurie padeda išspręsti daugybę skirtingų problemų. Pasaulyje, kuriame kiekvienas kompiuteris turėjo specialią liniją vienam iš šių orakulų, visas lengvai išspręstas problemas taip pat būtų lengva išspręsti, o p būtų lygi NP. Tačiau kiti, mažiau naudingi orakulai turi priešingą efektą. Šių orakulų apgyvendintame pasaulyje P ir NP būtų įrodyta skirtingai.
