Galderak azkar eta zehaztasunez erantzun ditzaketen gailu hipotetikoak tresna indartsu bihurtu dira konplexutasun konputazionalaren teorian.
Egin galdera bat 8 Bola Magiko bati, eta baiezko batekin, ezezko batekin edo zehaztasun gabeko zerbait amorragarriarekin erantzungo dizu. Guretzat haurrentzako jostailu bat besterik ez da, baina konputazioaren teorialariek antzeko tresna bat erabiltzen dute. Askotan imajinatzen dute orakulu izeneko gailu hipotetikoak kontsulta ditzaketela. Gailu horiek berehala eta zuzen erantzun diezaiekete galdera espezifikoei. Fantasiazko esperimentu mental horiek algoritmo berriak inspiratu dituzte eta ikertzaileei konputazioaren paisaia mapatzen lagundu diete.
Bideoa: Mark Belan – Copyright lizentziapean. Iturria: Quanta Magazine
Orakuluei hel egiten dieten ikertzaileek informatikaren azpieremu batean egiten dute lan, konplexutasun konputazionalaren teoria izenekoa. Problemen berezko zailtasunaz arduratzen dira, hala nola zenbaki bat lehena den ala ez zehaztea edo sare batean bi punturen arteko biderik laburrena aurkitzea. Problema batzuk erraz ebazten dira, beste batzuek askoz ere zailagoak dirudite, baina egiaztatzeko errazak diren konponbideak dituzte, eta beste batzuk berriz, errazak dira ordenagailu kuantikoentzat, baina itxuraz zailak ordenagailu arruntentzat.
Konplexutasunaren teorialariek itxurazko zailtasunean dauden desberdintasun horiek funtsezkoak diren ulertu nahi dute. Existitzen al da problema batzuetan berez zaila den zerbait, edo, besterik gabe, ez gara soluzio on bat aurkitzeko behar bezain argiak? Ikertzaileek galdera horiei heltzen diete problemak «konplexutasun motetan» sailkatuz —adibidez, problema erraz guztiak mota batean eta egiaztatzeko errazak diren problema guztiak beste batean— eta mota horien arteko harremanei buruzko teoremak frogatuz.
Zoritxarrez, badirudi zaila dela zailtasun konputazionalaren paisaia mapatzea. Beraz, 1970eko hamarkadaren erdialdean, ikertzaile batzuk konputazioaren arauak desberdinak balira zer gertatuko litzatekeen aztertzen hasi ziren. Eta hor sartzen dira orakuluak.
8 Bola Magikoak bezala, orakuluak baiezko eta ezezko galderak berehala erantzuten dituzten gailuak dira, bere barne funtzionamenduari buruz ezer erakutsi gabe. 8 Bola Magikoek ez bezala, beti erantzuten dute bai ala ez, eta beti dute arrazoi: fikziozkoak izatearen abantaila. Gainera, edozein orakuluk galdera mota jakin bati baino ez dio erantzungo, hala nola «Hau zenbaki lehena al da?».
Zergatik dira fikziozko gailu horiek mundu erreala ulertzeko baliagarriak? Laburbilduz, konplexutasun mota desberdinen arteko ezkutuko konexioak erakuts ditzakete.
Har ditzagun bi konplexutasun mota ospetsuenak. Ebazteko errazak diren problemak daude, ikertzaileek «P» deitzen diete, eta egiaztatzeko errazak diren problema motak, «NP» deitzen dietenak. Egiaztatzeko errazak diren problema guztiak ebazteko errazak al dira? Hala balitz, horrek esan nahiko luke NP P-ren berdina izango litzatekeela, eta enkriptazio guztia haustea erraza izango litzateke (beste ondorio batzuen artean). Konplexutasunaren teorialariek uste dute NP ez dela P‑ren berdina, baina ezin dute frogatu, nahiz eta 50 urte baino gehiago daramatzaten bi moten arteko harremana zehazten saiatzen.
Orakuluek lagundu diete hobeto ulertzen zerekin ari diren borrokan. Ikertzaileek hainbat problema ebazten laguntzen duten galderak erantzuten dituzten orakuluak asmatu dituzte. Ordenagailu bakoitzak orakulu horietako batekin zuzeneko lotura duen mundu batean, erraz egiazta daitezkeen problema guztiak ere erraz ebatziko lirateke, eta P eta NP berdinak izango lirateke. Baina hain baliagarriak ez diren beste orakulu batzuek kontrako efektua dute. Orakulu horiez beteriko mundu batean, P eta NP modu frogagarrian desberdinak izango lirateke.
Ikertzaileek ezagutza hori erabili dute P NP‑ren aurkako problema hobeto ulertzeko. P eta NP-ren arteko harremana zehazteko lehen saiakerek diagonalizazioa izeneko trikimailu dotore bat erabili zuten, informatikako beste emaitza garrantzitsu batzuetarako funtsezkoa. Hala ere, ikertzaileak laster konturatu ziren diagonalizazioan oinarritutako edozein froga ordenagailu bakoitzak orakulu bera kontsultatu ahal zuen edozein mundutan ere aplikatuko zela. Horrek arazoak ekarri zituen, orakuluek aldatu egin baitzuten P eta NP galderen erantzuna. Ikertzaileek diagonalizazioa erabili ahal izango balute mundu errealean P eta NP desberdinak direla frogatzeko, froga berak erakutsiko luke P eta NP desberdinak direla orakuludun mundu batean, non argi eta garbi baliokideak diren. Horrek esan nahi du P NP-ren aurkako problemaren diagonalizazioan oinarritutako edozein soluzio autokontraesankorra izango litzatekeela. Ikertzaileek ondorioztatu zuten teknika berriak beharko zituztela aurrera egiteko.
Orakuluak ere baliagarriak izan dira konputazio kuantikoaren azterketan. 1980ko eta 1990eko hamarkadetan, ikertzaileek fisika kuantikoa aprobetxatzeko moduak deskubritu zituzten, ordenagailu «klasiko» arruntentzat zailak ziruditen zenbait problema azkar ebazteko. Baina, problema horiek zailak dirudite edo benetan zailak dira? Modu batera edo bestera frogatzeak teknika matematiko erabat berriak eskatuko lituzke.
Horregatik, ikertzaileek ordenagailu kuantikoek orakuluak inplikatzen dituzten problemei nola heltzen dieten aztertu dute. Ahalegin horiek zeharkako ebidentzia eman dezakete ordenagailu kuantikoak benetan klasikoak baino ahaltsuagoak direla frogatzeko, eta ikertzaileei lagundu diezaiekete kualitatiboki berriak diren zereginak esploratzen, non ordenagailu kuantikoak nabarmendu daitezkeen. Batzuetan, aplikazio praktikoak ere izan ditzakete. 1994an, Peter Shor matematikari aplikatuak orakuluei buruzko emaitza berri bat oinarri hartu zuen zenbaki handiak faktorizatzeko algoritmo kuantiko azkar bat garatzeko. Lan horren ustezko zailtasuna gure lineako informazioa seguru mantentzen duten sistema kriptografikoetan oinarritzen da. Shorren aurkikuntzak ordenagailu kuantiko indartsuak eraikitzeko jarduera bati hasiera eman zion, eta gaur egun arte jarraitzen du.
Zaila da konplexutasunaren teoriaren etorkizuna iragartzea, baina eremuaren ibilbideari buruzko galdera guztiak ez dira erantzuten zailak. Ikertzaileek orakuluak kontsultatzen jarraituko dute? Seinaleek baietz diote.
Jatorrizko artikulua:
Ben Brubaker (2025). Why Computer Scientists Consult Oracles, Quanta Magazine, 2025ko urtarrilaren 16a. Quanta Magazine aldizkariaren baimenarekin berrinprimatua.