‘Alderantzizko matematikak’ problema zailen zailtasunaren zergatia azaldu nahian
Teknika metamatematikoak erabilita frogatu ahal izan da erabilita desberdinak diruditen teorema batzuk egiaz logikoki baliokideak direla.
Arazo zailei dagokienez, konputazioko zientzialariak trabatuta daudela dirudi. Adibidez, har dezagun problema ospetsu bat: mapa bateko hiri bakoitzetik behin igarotzen den ibilbide zirkular laburrena aurkitzearena. «Merkataritzako bidaiariaren problema» ebazteko metodo ezagun guztiak oso mantsoak dira mapak hiri asko dituenean, eta ikertzaileen ustez ez dago hobeto egiteko beste modurik. Baina inork ez daki hori nola frogatu.
Duela 50 urte baino gehiagotik, konplexutasun konputazionalaren teoriaren ikertzaileak saiatu dira baieztapen intuitiboak, «merkataritzako bidaiariaren problema zaila da» esaterako, matematikako teorema eztabaidaezin bihurtzen, baina ez dute arrakasta handirik izan. Horrekin zerikusia duen galdera lausoago bati erantzun zehatzagoak aurkitzen ere saiatzen dira: zergatik ez dute arrakastarik izan beren frogek?
Egiteko horrek frogatze matematikoaren prozesua bera analisi matematikoaren xedetzat hartzen du, eta zailtasunagatik ezaguna den alor batekoa da: metamatematika. Metamatematikariek oinarrizko suposizioak edo axiomak aztertzen dituzte, froga guztien abiapuntuak izaten baitira. Hasierako axioma horiek aldatu eta aldaketek frogatu daitezkeen teoremetan zer eragin duten aztertzen dute. Metamatematika aplikatzen denean konplexutasunaren teorian, helburua da zehaztea axioma taldeek zer frogatu dezaketen eta zer ez zailtasun konputazionalari buruz. Horren bidez, ikertzaileek espero dute ulertzea zergatik ez duten aurrera egin problema batzuk zailak direla frogatzeko egindako saioek.
Iaz argitaratutako artikulu batean, hiru ikertzailek beste ikuspegi bat hartu zuten. Matematikariek milaka urtean erabilitako metodoa alderantzikatu egin zuten: teorema bat frogatzeko axiomen multzo estandar batetik abiatu ordez, axioma baten ordez teorema bat jarri zuten eta axioma hori frogatu. Alderantzizko matematika bezala ezagutzen den ikuspegi horren bidez, konplexutasunaren teoriaren teorema ezberdin asko, egiaz, baliokideak direla frogatu zuten.
«Harritu egin ninduen zenbat aurreratu zuten ikusteak», dio Marco Carmosino IBMko konplexutasunaren arloko teorialariak. «Jendeak hau ikusiko du eta esango du: “Horregatik sartu nintzen metamatematikan”».
Usoekin frogak
Alderantzizko matematikari buruzko artikuluaren historia 2022ko udan hasi zen, Lijie Chen, konplexutasunaren teorialaria eta gaur egun Berkeleyko (Kalifornia) Unibertsitateko irakaslea, doktoregoa amaitzen ari zenean. Ohi baino denbora libre gehiago zuenez, hilabete batzuetan metamatematika aztertzea erabaki zuen.
«Graduatzen ari nintzenez, ez nuen ikerketa-lan handirik», azaldu du Chenek. «Zerbait berria ikasi behar nuela pentsatu nuen».
Irakurtzen ari zela Chen hausnartzen hasi zen konplexutasunaren teoriako adar bati buruz, komunikazioaren konplexutasuna izenekoaz, zeinak bi pertsona edo gehiagok egiteko jakin batzuk gauzatzeko zenbat informazio trukatu behar duten aztertzen baitu. Alor honetako problema soilenetako bat, «berdintasunaren problema» izenaz ezagutzen dena, lankidetzako joko baten antzekoa da. Bi jokalari zeroz eta batez, hau da, bitez, osatutako kate independenteekin hasten dira. Xedea da ahalik eta komunikazio gutxien erabiltzea, bi kateak berdin-berdinak ote diren zehazteko. Estrategiarik soilena da jokalarietako batek katea osoa igortzea, besteak egiaztatzeko. Galdera da jarduteko modu efizienteagorik ba ote den.
Konplexutasunaren teorialariek duela hamarkada batzuk frogatu zuten erantzuna ezezkoa dela. Berdintasunaren problema ebazteko, jokalariek gutxienez igorri beharreko bit kopuruak katea osoaren luzeraren adinakoa izan behar du. Luzera hori beharrezko komunikazio kopuruaren behe-borne bat da.
Chen ez zen egon problemaren behe-borneari begira, baizik eta frogatzeko erabili zen moduari begira. Ezagutzen diren froga guztiak teoria soil baten mende daude, usategiaren printzipioa esaten zaio, eta horren arabera usategiak baino uso gehiago egonez gero, gutxienez usategietako batek uso bat baino gehiago izango du. Agerikoa dirudien arren, printzipio hori oso tresna boteretsua da konplexutasunaren teorian eta matematiketako beste alor batzuetan.
Chenek pista iradokitzaile bat aurkitu zuen: berdintasunaren problemaren eta usategiaren printzipioaren arteko erlazioak alderantziz ere funtziona zezakeen. Erraza da usategiaren printzipioa erabiltzea berdintasunaren problemaren behe-bornea frogatzeko. Kontua zen behe-borne hori erabili ote zitekeen usategiaren printzipioa frogatzeko.
Berdintasun kezkagarria
Chenek Jiatu Liri aipatu zion bere ideia. Li garai hartan graduko ikaslea zen Tsinghuako Unibertsitatean, eta Chenek harekin idatzi zuen zuela gutxi artikulu bat. Konexioa formalizatzeko, lan egiteko axioma talde bat hautatu beharra zuten. Metamatematikan ohikoa da konbentzionalak baino axioma mugatzaileagoak erabiltzea, sistema ahulago horiei esker zehatzago identifikatu baitaitezke teorema desberdinen arteko harremanak. Chenek eta Lik hautatu zuten axioma taldea, PV1 delakoa, oso erabilia da. PV1 behar bezain indartsua da bere kabuz frogatu ahal izateko konplexutasun konputazionaleko teoriaren teorema garrantzitsu batzuk. Axioma gehigarri gisa usategiaren printzipioaren bertsio jakin bat erantsiz gero, berdintasunaren problemaren behe-bornea ere frogatu daiteke. 2022ko abenduan Li eta Chenek formalki frogatu zuten, Chenek uste bezala, frogak balio zuela bi teoremen egitekoa trukatuta ere.
Berdintasunaren problemaren behe-bornea usategiaren printzipiotik abiatuta frogatzeak, eta alderantziz, esan nahi du PV1en esparru logikoaren barruan bi teoremak baliokideak direla. Lik eta Chenek emaitza hori Warsickeko unibertsitateko konplexutasunaren teorialari Igor Oliveirari azaldu ziotenean, hirurak ohartu ziren alderantzizko matematikaren ikuspegia konplexutasunaren teoriako beste alor batzuetan ere erabil zitekeela. Hurrengo hilabeteetan sistematikoki frogatu zituzten beste emaitza askoren arteko baliokidetasunak.
«Hasieran bi emaitza baliokide besterik ez genuen», azaldu du Chenek. «Orain sare bat dugu».
Konexiorik deigarrienak lotu egin zituen usategiaren printzipioaren bertsio bera eta konplexutasunaren teoriako hasierako ikasturteetan ikasten den lehenengo teoremetako bat. «Ezinbesteko klasikoa» da Carmosinoren esanetan eta behe-borne bat ezartzen du ordenagailu teoriko mota batek —zinta bakarreko Turingen makinak— zehaztu dezan zeroz eta batez osatutako kate bat palindromoa den, hau da, ezkerretik eskuinera zein eskuinetik ezkerrera berdin irakurtzen den. Alderantzizko matematikaren bidez Lik, Chenek eta Oliveirak frogatu zuten PV1aren barruan teorema hori usategiaren printzipioaren baliokidea dela.
«Norbaitek esan izan balitz, ez nukeen sinetsiko», aitortu du Chenek. «Erabat absurdoa dirudi».
Baliokidetasun hori harrigarria da bi teoremek, itxura batera, oso desberdinak baitirudite. Usategiaren printzipioa ez dago, berez, kalkuluari lotuta: zenbaketari buruzko oinarrizko baieztapen bat da. Palindromoentzako behe-bornea, aldiz, konputazioko eredu jakin bati buruzkoa da. Emaitza berriaren arabera, teorema itxuraz espezifikoek uste zena baino irismen askoz orokorragoa dute.
«Horrek esan nahi du ulertu nahi ditugun konplexutasunaren behe-borne horiek askoz funtsezkoagoak direla», dio Oliveirak.
Aztertu gabeko lurraldea
Baliokidetasunen sare horri esker, PV1en mugak ere argitu ahal izan dira. Ikertzaileek bazituzten arrazoiak uste ahal izateko usategiaren printzipioa ezin dela frogatu PV1en axiometatik abiatuta besterik gabe; beraz, Liren, Chenen eta Oliveiraren emaitzek esan nahi dute gainerako teorema baliokideak ere seguru asko ezingo direla frogatu sistema horretan.
«Zoragarria da», dio Ján Pichek, konplexutasunaren teorialariak Oxfordeko Unibertsitatean, 2014an PV1en potentziari buruz emaitza garrantzitsua lortu zuenak. Dena dela, ohartarazi zuen alderantzizko matematikak bereziki ikuspegi garrantzitsua izan dezakeela jada ezagunak diren teoremen arteko lotura berriak agerrarazteko. «Orain arte baiezta dezakegunez, ez digute gauza handirik esaten oraindik nola frogatu ez dakigun enuntziatuen konplexutasunari buruz».
Aztertu gabeko lurralde hori ulertzea, oraindik ere, urruneko helburua da metamatematikako ikertzaileentzat. Dena dela, horrek ez du zapuztu Lik alor horretan duen entusiasmoa. Graduondoko ikasketak Massachusettseko Institutu Teknologikoan hasi zituen 2023an eta duela gutxi idatzi du metamatematikari buruzko 140 orriko gidaliburu bat konplexutasunaren teorialarientzat. Joera zabalago baten adibidea da: zenbait hamarkada apur bat baztertuta egon ondoren, metamatematikak gero eta arreta handiagoa erakartzen du ikertzaileen komunitatean, arloari ikuspegi berriak ematen ari baitira.
«Jendea nekatuta dago blokeatuta egoteaz», esan du Carmosinok. «Urrats bat atzera egin eta oinarriak lantzeko garaia da».
Jatorrizko artikulua:
Ben Brubaker (2025). ‘Reverse Mathematics’ Illuminates Why Hard Problems Are Hard, 2025ko abenduaren 1a. Quanta Magazine aldizkariaren baimenarekin berrinprimatua.