P vs NP problema

P vs NP problema informatika teorikoan konpondu gabeko problema garrantzitsua da. Termino informaletan esanda, problema baten ebazpena azkar egiaztatzea posible bada ea horrelakoetan ebazpen azkar aurkitzea ere posiblea ote den galdetzen du.

Goian erabilitako azkar termino informalak denbora polinomikoan exekutatzen den zeregina ebazten duen algoritmo baten existentzia esan nahi du; hau da, zeregina burutzeko denbora funtzio polinomiko gisa aldatzen da algoritmoaren sarreraren tamainaren arabera (esaterako, datu-kopurua handitzerakoan, ebazpena lortzeko behar den denbora ez dela handitzen funtzio esponentzial gisa, motelago baizik). Galdera edo problema bat ebazteko posible baldin bada denbora polinomikoan erantzuna eman dezakeen algoritmo bat aurkitzea problema horren klase orokorra "P" edo "P klasea" dela esaten da. Galdera batzuetarako, ez dago erantzuna azkar aurkitzeko modu jakinik, baina, erantzuna zein den erakusten duen informazioa ematen bazaio, erantzuna azkar egiaztatzeko aukera dago. Erantzuna denbora polinomikoan egiazta daitekeen galderen klasea NP da, «denbora polinomiko ez determinista» ("Nondeterministic Polynomial time") esan nahi duena

P versus NP galderarako erantzun batek zehaztuko luke ea denbora polinomikoan egiazta daitezkeen problemak denbora polinomikoan ere ebatzi daitezkeen. P ≠ NP frogatuko balitz (uste zabala hori da), horrek esan nahiko luke NPn badirela problemak zeinetan ebazpena bilatzea ebazpena egiaztatzea baino zailagoa den; eta ezingo lirateke denbora polinomikoan ebatzi, baina erantzuna denbora polinomikoan egiaztatzea bai.

Problemari informatikako problema ireki garrantzitsuena deitu izan zaio. Teoria konputazionalean problema garrantzitsu bat izateaz gain, proba batek inplikazio sakonak izango lituzke matematika, kriptografia, algoritmoen ikerketa, adimen artifiziala, jokoen teoria, multimedia prozesatzea, filosofia, ekonomia eta beste hainbat esparrutan.

Konplexutasun konputazionalean aztertzen diren baliabideak hauek dira:

• Denbora: algoritmo batek problema bat ebazteko erabiltzen dituen exekuzio-urratsen kopurua. Normalean ez da kalkulatzen zenbaki zehatz bat, zenbaki horren estimazio bat edo hurbilpen bat baizik.
• Espazioa: problema ebazteko erabilitako memoriaren tamainaren hurbilpen bat.

Problemak multzo edo konplexutasun klaseetan sailkatzen dira (L, NL, P, PCOlea, NP, NP-Complete, NP Hard...). Artikulu hau P eta NP klaseetan zentratuko da.

Clay Mathematics Institute-k hautatutako zazpi Millennium Prize Problemetako bat da, eta horietako bakoitzak 1.000.000 dolarreko saria du lehen irtenbide zuzenarentzat.

Adibidea

Demagun Sudokua: jokalariari partzialki betetako zenbaki-sare bat ematen zaion eta, arau batzuk jarraituz, sarea osatzen saiatzen den jokoa. Sudoku sare osatugabea izanik, edozein tamainatakoa, ba al dago konponbide legal bat gutxienez? Proposatutako edozein soluzio erraz egiaztatzen da, eta soluzio bat egiaztatzeko denbora poliki-poliki (polinomikoki) hazten da, sarea handitu ahala. Hala ere, irtenbideak aurkitzeko algoritmo ezagun guztiek, adibide zailetarako, sarea esponentzialki handitu ahala hazten doan denbora hartzen dute. Beraz, Sudokua NPn dago (azkar egiazta daiteke), baina ez dirudi Pn dagoenik (azkar konpon daiteke). Beste milaka Problema antzekoak dirudite egiaztatzeko azkarrak, baina konpontzeko motelak direlako. Ikertzaileek frogatu dute NPko problema askok propietate gehigarria dutela, horietako edozeinen soluzio azkarra erabil daitekeela NPko beste edozein problema konponbide azkar bat eraikitzeko: NP-Complete izeneko propietatea. Bilaketa-hamarkadetan, ez zaio irtenbide azkarrik eman problema horietako bati ere ez, beraz, zientzialari gehienek susmatzen dute problema horietako bat ere ezin dela azkar konpondu. Hori, ordea, ez da inoiz frogatu.

Historia

P versus NP problemaren enuntziatu zehatza 1971n sartu zuen Stephen Cook-ek «The complexity of theorem proving procedures» artikuluan (eta independenteki Leonid Levin-ek 1973an).

P versus NP problema, formalki, 1971n definitu bazen ere, bazeuden aurretiazko susmoak problemei, frogatzeko zailtasunari eta balizko ondorioei buruz. 1955ean, John Nash matematikariak gutun bat idatzi zion AEBko NSAri, eta bertan espekulatzen zuen nahikoa konplexua den kode bat pizteak denbora esponentziala beharko zukeela gakoaren luzeran Frogatuz gero (eta Nash nahiko eszeptikoa zen), gaur egun P ≠ NP deitzen dena suposatuko luke horrek, proposatutako gako bat denbora polinomikoan erraz egiazta baitaiteke. Oinarrizko problemaren beste aipamen bat Kurt Gödelek John von Neumann-i 1956ko idatzitako gutun batean gertatu zen. Gödelek galdetu zuen ea teoremaren froga (gaur egun ko-NP-Complete dela ezagutzen dena) denbora koadratiko edo linealean ebatzi zitekeen, eta ondorio bat adierazi zuen: hala balitz, froga matematikoen aurkikuntzak automatizatu zitezkeen.

Algoritmoen ordena

T(n)-ren bidez, sarrera n tamainakoa duen algoritmo baten exekuzio-denbora adierazi ohi da. Algoritmoak hartzen duen denbora hori f(n)-ren ordenakoa dela esango da baldin eta soilik baldin k konstanteak existitzen badu, non instantzia bakoitzeko problema k * f(n) segundotan (mikrosegundotan, minututan...) gehienez ebazten baita. k konstanteari konstante biderkatzailea deritzo.

Segundotan dela esatea erabat arbitrarioa da konstantearen balioa aldatzea besterik ez baita beharko unitatea beste bat izateko. Bestalde, gaur egun makina estandarrik ez dagoenez, ezingo da bat eredutzat hartu (ik. RAM). Honen guztiaren ondorioz, eraginkortasunak unitaterik ez duela esan dezakegu.

Algoritmoen konplexutasuna neurtzeko gehienetan erabiltzen diren ordenak hauek dira:

Maiz agertzen diren ordenak		Algortimoaren konplexutasuna
n (n -ren ordenakoa)	→	algoritmoa lineala da
n2	→	koadratikoa
n3	→	kubikoa
nk	→	polinomikoa
an	→	esponentziala

non aurreko k eta a konstante egokiak diren.

Kontzeptu hauek algoritmo jakin baten ordena kalkulatzerakoan erabiltzen dira, beti ere, beste algoritmo batzuen ordenekin konparatu ahal izateko, non beste algoritmo haork ere problema bera ebazten duten. Honela eraginkorrena zein den muga dezakegu. Azkarrena, memoria kudeaketan hoberena; oro har, baliabideen kudeatzaile onena zein den mugatu dezakegu.

Bibliografia

• Rachel Crowell. (28 May 2021). «The Top Unsolved Questions in Mathematics Remain Mostly Mysterious Just one of the seven Millennium Prize Problems named 21 years ago has been solved» www.scientificamerican.com. ""Arazo horrek esan nahi du ea erraz egiaztatzen diren galderek (NP izeneko kontsulta mota bat) konponbide errazik ere ote duten (P izeneko klase bat)."
• Hosch, William L (11 August 2009). "P versus NP problem mathematics". Encyclopædia Britannica. "Demagun unibertsitateko laurehun ikasleko talde batentzat ostatuak antolatzen ari zarela. Lekua mugatua da, eta ehun ikaslek soilik jasoko dute logela-tokia. Arazoak zailtzeko, Dekanoak bateraezin diren hainbat ikasle-bikote eman ditu, eta azken toki-banaketan zerrenda horretako bikoterik ager ez dadin eskatu du. NP arazo deritzonaren adibide bat da hori informatikarientzat..."
• «P vs NP Problem» www.claymath.org (Cook, Levin).

Bibliografia osagarria

• Cormen, Thomas (2001). Introduction to Algorithms. Cambridge: MIT Press. ISBN 978-0-262-03293-3
• Garey, Michael; Johnson, David (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Company. ISBN 978-0-7167-1045-5
• Goldreich, Oded (2010). P, NP, and NP-Completeness. Cambridge: Cambridge University Press. ISBN 978-0-521-12254-2 Online drafts
• Immerman, N.. (1987). «Languages that Capture Complexity Classes» SIAM Journal on Computing 16 (4): 760–778.  doi:10.1137/0216051..
•  Papadimitriou, Christos (1994). Computational Complexity. Boston: Addison-Wesley. ISBN 978-0-201-53082-7

Kanpo estekak

• Fortnow, L.; Gasarch, W.. Computational complexity. .
• Aviad Rubinstein's Hardness of Approximation Between P and NP, winner of the ACM's 2017 Doctoral Dissertation Award.
• P vs. NP and the Computational Complexity Zoo. 26 August 2014.

• Datuak: Q746242