Usategiak baino uso gehiago daudenean, zenbait hegazti elkartu behar dira. Bistakoa den baieztapen horrek, eta haren kontrakoak, konexio sakonak ditu matematiken eta informatikaren arlo askorekin.
Hobe da txori bat eskuan ehun hegan baino, dio esaerak, baina informatikarientzat onena hauxe da: bi txori zulo batean. Izan ere, lekua partekatzen duten hegazti horiek usategiaren printzipioa izeneko teorema matematiko baten protagonistak dira. Teorema erraza dirudi, baina engainagarria da oso. Labur azaltzeko: hamar uso elkartzen badira bederatzi usategitan, gutxienez bi usok zuloa partekatu behar dute. Eta listo, hori da dena.
«Usategiaren printzipioak irribarrea ateratzen digu», komentatu du Christos Papadimitriouk, Columbiako Unibertsitateko informatikari teorialariak. «Elkarrizketarako gai bikaina da».
Hala ere, usategiaren printzipioa ez da soilik txoriei buruzkoa. Benetan sinplea dirudien arren, tresna garrantzitsua da informatika teorikoaren proiektu nagusian lan egiten duten ikertzaileentzat: problemen arteko konexio ezkutuak mapatzean, alegia.
Usategiaren printzipioa objektuak kategorietara esleitzen diren eta objektuen kopurua kategoria kopurua baino handiagoa den edozein egoeratan aplika daiteke. Adibidez, 30.000 eserleku dituen eta bete-beteta dagoen futbol zelai batean, bertaratutako batzuek lau digituko pasahitz edo PIN berbera izango dute beren bankuko txarteletan. Kasu horretan, usoak dira futbol zaleak eta zuloak dira 10.000 PIN posibleak (0000tik 9999ra). Horrek esan nahi du digitu aukera txikiagoa dela pertsonen guztizkoa baino; eta, beraz, zaleetako batzuek digitu berberak izango dituzte.
Frogapen hori azpimarratzekoa da oso sinplea delako, baina baita ezkutuan uzten duenagatik ere. Zerbait existitzen dela frogatzeko metodo matematiko asko «konstruktiboak» dira; hau da, nola ebatzi ere erakusten dute. Frogapen «ez konstruktiboek», baina, hala nola usategiaren printzipioak, ez dute propietate hori. Futbol zelaiaren adibidean, badakigu pertsona batzuek PIN berbera izango dutela, baina ez dakigu zein diren pertsona horiek. Harmailetan ibil ginatekeen eta banan-banan galdetu. Baina, ez al dago beste bide errazagorik?
Horrelako galderak, problemak ebazteko modurik efizienteena aurkitzeari buruzkoak, ezinbestekoak dira konplexutasun konputazionalaren teoria izeneko informatikaren adarrean. Konplexutasunaren teorialariek horrelako galderak ikertzen dituzte, eta problemak zenbait klasetan sailkatzen dituzte, partekatzen dituzten propietateetan oinarrituta. Batzuetan, aurrerapen bat lortzeko lehenengo urratsa problemak sailkatzeko klase berri bat definitzea besterik ez da, ikertzaileek aurretik ikertu ez dutena.
Eta horixe bera gertatu zen 1990. urtean, Papadimitriouk eta konplexutasunaren beste teorialari batzuek problema klase berriak ikertzen hasi zirenean, zeinetan xedea baita existitu behar duen zerbait aurkitzea, usategiaren printzipioan edo beste frogapen ez konstruktiboren batean oinarrituta. Lan ildo horrek aurrerapen handiak ekarri ditu informatikaren eremu askotan, kriptografiatik hasi eta joko teoria algoritmikora arte.
2020ko urtarrilean, Papadimitriouk 30 urte zeramatzan usategiaren printzipioari buruzko hausnarketa lanetan. Hori dela eta, aho zabalik geratu zen bere ohiko kolaboratzaile batekin hizketan ari zela, ordura arte pentsatu ez zuten printzipioaren ikuspegi soil batera iritsi zirenean: zer gertatzen da zuloak baino uso gutxiago baldin badaude? Kasu horretan, usoak non gorde gorabehera, zulo hutsak egongo dira. Berriro ere, guztiz bistakoa dirudi. Baina, usategiaren printzipioari buelta emateak ba al du ondorio matematiko interesgarririk?
Bada, badirudi «usategi hutsaren» printzipioa jatorrizko teorema bera dela, beste izen bat hartuta; baina hori ez da egia. Pixka bat ezberdina da, eta, hori dela eta, tresna berri eta eraginkorra da problema konputazionalak sailkatzeko.
Usategi hutsaren printzipioa ulertzeko, itzul gaitezen bankuko txartelaren adibidera. Futbol zelaia ahaztu eta 3.000 eserlekuko kontzertu areto bat imajinatuko dugu; hau da, lau digituko PIN posibleen kopurua baino eserleku gutxiago dituen eremu bat. Usategi hutsaren printzipioak dio PIN posibleetako batzuk ez direla bertan irudikatuta egongo. Hala ere, falta diren PIN horietako bat aurkitu nahi badugu, badirudi bide bakarra dela pertsona guztiei banan-banan beren PIN zenbakia galdetzea. Orain arte, kutxatilategi hutsaren printzipioa haren kontrako alderdi famatua bezalakoa da.
Aldea soluzioak egiaztatzeko zailtasunean datza. Demagun norbaitek esaten duela futbol zelaian PIN berbera duten bi pertsona aurkitu dituela. Jatorrizko usategiaren planteamenduari dagokion kasu horretan, bada modu erraz bat baieztapen hori egiaztatzeko: bi pertsona horiekin zuzenean egiaztatzea. Baina kontzertu aretoaren kasuan, imajinatu norbaitek esaten duela ez dagoela 5926 PIN zenbakia duen pertsonarik. Kasu horretan, ezingo genuke hori egiaztatu bertan dauden guztiei zein PIN zenbaki duten galdetu gabe. Horrenbestez, usategi hutsaren printzipioa askoz konplexuagoa da konplexutasunaren teorialarientzat.
Papadimitriou usategi hutsaren printzipioari buruz hausnartzen hasi eta bi hilabetera, gaia atera zuen graduondoko ikasle izango zen batekin hizketan ari zela. Une hori fresko dauka gogoan; izan ere, COVID-19aren itxialdien aurretik izan zuen azkeneko zuzeneko elkarrizketa izan zen. Hurrengo hilabeteetan, etxetik atera ezin zenean, konplexutasunaren teoriari begira problemak dituen inplikazioak aztertu zituen. Azkenik, bere kideekin batera, artikulu bat argitaratu zuen usategi hutsaren printzipioari esker bermatutako soluzioak dituzten bilaketa problemei buruz. Interes berezia zuten usategi asko zeuden problemetan; hau da, uso baino usategi askoz gehiago daudenetan. Konplexutasunaren teoriako akronimo konplikatuen tradizioari jarraikiz, problema klase hori APEPP izendatu zuten, ingelesezko siglengatik: «usategi huts polinomial oparoaren printzipioa».
Klase horretako problemetako bat Claude Shannon informatikako aitzindariaren duela 70 urteko frogapen famatuan inspiratu zen. Shannonek frogatu zuen problema konputazional gehienak berez ebazteko zailak izan behar direla, usategi hutsaren printzipioan (hark ez zion hala deitu) oinarritutako argumentu bat erabiliz. Nolanahi ere, zenbait hamarkadatan, informatikariak saiatu dira frogatzen, arrakastarik izan gabe, problema jakin batzuk benetan zailak direla. Falta diren bankuko txartelen PINak bezalaxe, problema zailak ere existitu behar dira, identifikatu ezin baditugu ere.
Historikoki, ikertzaileek ez dute problema konplexuen bilaketa prozesua matematikoki azter daitekeen bilaketa problematzat hartu. Papadimitriouren ikuspegiak, baina, prozesu hori multzokatu zuen usategi hutsaren printzipioarekin lotura duten beste bilaketa problema batzuekin, eta bazuen konplexutasunaren teorian duela gutxi eginiko lanaren zati handi baten kutsu autoerreferentzial bereizgarria: konplexutasun konputazionala frogatzeko zailtasunari buruz arrazoitzeko modu berri bat eskaintzen zuen.
“Konplexutasunaren teoriaren eginkizuna aztertzen ari zara konplexutasunaren teoria erabilita”, azaldu du Oliver Kortenek, Columbiako ikertzaileak.
Korten pandemia aurretik Papadimitriourekin usategi hutsaren printzipioari buruz eztabaidatu zuen ikaslea da. Columbiara iritsi zen Papadimitriourekin lan egiteko, eta graduondokoaren lehenengo urtean frogatu zuen problema konputazional konplexuen bilaketa estuki lotuta zegoela APEPP klaseko gainerako problema guztiekin. Zentzu matematikoki espezifikoan, problema horretan egiten den edozein aurrerapen automatikoki izango da informatikari eta matematikariek denbora luzez ikertutako beste problema askotako aurrerapen, hala nola azpiegitura sinplerik ez duten sareen bilaketakoa.
Kortenen artikuluak beste ikertzaile batzuen interesa piztu zuen berehala. «Benetan harritu nintzen ikusi nuenean», esan du Rahul Santhanamek, Oxfordeko Unibertsitateko konplexutasunaren teorialariak. «Benetan zirraragarria da». Ordutik, Santhanamek eta beste ikertzaile batzuek Kortenen aurrerapena aprobetxatu dute zailtasun konputazionalaren eta ausazkotasunaren arteko konexioei buruzko emaitza berrien serie bat frogatzeko.
«Benetan aberasgarria da», esan du Papadimitriouk. «Konplexutasunaren arloko problema garrantzitsuen muinean jo du».
Jatorrizko artikulua:
Ben Brubaker. (2025). How a Problem About Pigeons Powers Complexity Theory, Quanta Magazine, 2025eko apirilaren 4a. Quanta Magazine aldizkariaren baimenarekin berrinprimatua.