P vs NP problema

P vs NP problema informatika teorikoan konpondu gabeko problema garrantzitsua da. Termino informaletan, konponbidea azkar egiazta daitekeen arazoak ea azkar konpondu daitekeen ere 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,denbora esponentzialaren aurkakoa). Algoritmo batzuek denbora polinomikoan erantzuna eman dezaketen galderen klase orokorra "P" edo "P klasea" 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» esan nahi duena

P versus NP galderari erantzunak denbora polinomikoan egiazta daitezkeen problemak denbora polinomikoan ere ebatzi daitezkeen zehaztuko luke. Gertatzen bada P ≠ NP, uste zabala duen bezala, NPn zenbatzea baino zailagoa den problemak badirela esan nahiko luke, eta ezingo lirateke denbora polinomikoan ebatzi, baina erantzuna denbora polinomikoan egiazta zitekeen.

Arazoari informatikako arazo ireki garrantzitsuena deitu izan zaio. Teoria konputazionalean arazo 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 arazo bat ebazteko erabiltzen duen exekuzio-urratsen arteko hurbilketa baten bidez.

– Espazioa: arazoa ebazteko erabilitako memoria kopuruaren hurbilketa.

Arazoak 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 USDko 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 arazo 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 arazoren konponbide azkar bat eraikitzeko: NP-Complete izeneko propietatea. Bilaketa-hamarkadetan, ez zaio irtenbide azkarrik eman arazo horietako bati ere ez, beraz, zientzialari gehienek susmatzen dute arazo 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 arazoa, formalki, 1971n definitu bazen ere, bazeuden aurretiazko susmoak arazoei, 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 arazoaren 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.

Erreferentziak

Oharrak

Iturriak 
 
 Hosch, William L (11 August 2009). "P versus NP problem mathematics". Encyclopædia Britannica. Retrieved 20 June 2021

Irakurketa gehiago 
 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. 
 Goldreich, Oded (2010). P, NP, and NP-Completeness. Cambridge: Cambridge University Press.   
Online drafts
 
  Papadimitriou, Christos (1994). Computational Complexity. Boston: Addison-Wesley.

Kanpo estekak 
 
 Aviad Rubinstein's Hardness of Approximation Between P and NP, winner of the ACM's 2017 Doctoral Dissertation Award.
 

Informatika