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^{[oh 1]}

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^[1]. 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[aldatu | aldatu iturburu kodea]

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[aldatu | aldatu iturburu kodea]

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^[2]).

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^[3] 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^[4], eta ondorio bat adierazi zuen: hala balitz, froga matematikoen aurkikuntzak automatizatu zitezkeen.

Erreferentziak[aldatu | aldatu iturburu kodea]

↑ Fortnow, Lance. (2009). «The status of the P versus NP problem» Communications of the ACM 52 (9): 78–86. doi:10.1145/1562164.1562186..
↑ (Errusieraz) L. A. Levin. (1973). Пробл. передачи информ 93: 115–116..
↑ NSA. (2012). Letters from John Nash. .
↑ Hartmanis, Juris. «Gödel, von Neumann, and the P = NP problem» Bulletin of the European Association for Theoretical Computer Science 38: 101–107..

Oharrak[aldatu | aldatu iturburu kodea]

↑ Turing makina ez deterministikoa aurreko egoerak zehazten ez duen egoera batera mugi daiteke. Horrelako makina batek NP problema bat denbora polinomikoan ebatzi lezake erantzun zuzeneko egoeran eroriz (zortez), eta gero konbentzionalki egiaztatuz. Horrelako makinak ez dira praktikoak problema errealistak ebazteko, baina eredu teoriko gisa erabil daitezke.

Iturriak[aldatu | aldatu iturburu kodea]

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.
Hosch, William L (11 August 2009). "P versus NP problem mathematics". Encyclopædia Britannica. Retrieved 20 June 2021
«P vs NP Problem» www.claymath.org (Cook, Levin).

Irakurketa gehiago[aldatu | aldatu iturburu kodea]

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[aldatu | aldatu iturburu kodea]

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

[2] Fortnow, Lance. (2009). «The status of the P versus NP problem» Communications of the ACM 52 (9): 78–86. doi:10.1145/1562164.1562186..

[3] (Errusieraz) L. A. Levin. (1973). Пробл. передачи информ 93: 115–116..

[4] NSA. (2012). Letters from John Nash. .

[5] Hartmanis, Juris. «Gödel, von Neumann, and the P = NP problem» Bulletin of the European Association for Theoretical Computer Science 38: 101–107..

[1] Turing makina ez deterministikoa aurreko egoerak zehazten ez duen egoera batera mugi daiteke. Horrelako makina batek NP problema bat denbora polinomikoan ebatzi lezake erantzun zuzeneko egoeran eroriz (zortez), eta gero konbentzionalki egiaztatuz. Horrelako makinak ez dira praktikoak problema errealistak ebazteko, baina eredu teoriko gisa erabil daitezke.

[oh 1]

[1]

[2]

[3]

[4]