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

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^[1]. 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 aurkezten zuen Stephen Cook-ek «The complexity of theorem proving procedures» artikuluan (eta independenteki Leonid Levin-ek 1973an^[2]).

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

Testuingurua

P eta PE konplexutasun klaseen arteko erlazioa konplexutasun konputazionalaren teorian aztertzen da, hori konputazioaren teoriaren zati bat da, arazo jakin bat konpontzeko konputazioan zehar behar diren baliabideak aztertzen dituena. Baliabide ohikoenak denbora (zenbat urrats hartzen dituen problema bat ebazteko) eta memoria (zenbat memoria behar den problema bat ebazteko) dira.

Analisi sakon horretako denbora analizatzeko konputagailuaren eredu bat behar da. Kasu gehienetan, eredu horiek ordenagailua determinista (ordenagailuaren egungo egoera eta edozein sarrera kontuan hartuta, ordenagailuak har dezakeen ekintza bakarra dagoela) dela eta sekuentziala (ekintzak bata bestearen atzetik egiten dituela) dela suposatzen dute.

Teoria honetan, P klasea makina sekuentzial determinista batean konpon daitezkeen erabaki-problema guztietan datza, sarreraren tamainako iraupen polinomio batean. Erabaki-arazo horiek ondoren zehazten dira.

NP klasea, polinomio denboran, informazio zuzena kontuan hartuz, soluzio positiboak egiaztatu daitezkeen erabaki problema guztietan datza. Bestela esanda, soluzioa makina ez-determinista batean polinomioan denboran aurki daiteke.^[5]

Argi eta garbi, P ⊆ NP da. Zalantzarik gabe, informatika teorikoan ireki den arazorik handiena bi klase horien arteko erlazioari buruzkoa da:

P eta NP berdinak ahal dira?

2002tik, William Gasarchek hiru inkesta egin ditu gai horri eta horrekin lotutako beste batzuei buruz.^[6]^[7]^[8] P ≠ NP delaren konfiantza handituz joan da urtear igaro adina, zeren 2019an % 88k uste zuen P ≤ NP zela, bestalde, 2012an, % 83k eta 2002an % 61k. Baina, 2019rako zientzialarien %99k uste dute P ≠ NP dela.^[8] Inkesta horiek ez dute inplikatzen P = NP, Gasarchek berak esan zuen: "Horrek ez gaitu hurbiltzen P=?NP ebaztera, ezta noiz ebatziko den jakitera ere; aro honen iritzi subjektiboari buruzko txosten objektibo bat izaten saiatzen da".

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

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

Algoritmoen konplexutasuna neurtzeko gehienetan erabiltzen diren ordenak hauek dira:^[9]

Maiz agertzen diren ordenak		Algortimoaren konplexutasuna
n (n -ren ordenakoa)	→	algoritmoa lineala da
n²	→	koadratikoa
n³	→	kubikoa
n^k	→	polinomikoa
aⁿ	→	esponentziala

non aurreko k eta a konstante egokiak diren.

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

Arazo zailagoak

Ez dakigu P = NP den ala ez, baina badakizkigu P-tik kanpo dauden problemak zeintzuk diren. P klasea exekuzio-denbora polinomioaren arabera definitzen den bezala, EXPTIME klasea exekuzio esponentzialeko denbora duten erabaki-problema guztien multzoa da. Beste modu batera esanda, EXPTIMEn edozein problema O(2^p(n)) denboran konpondu daiteke Turingen makina determinista baten bidez, non p(n) n-ren funtzio polinomiko bat den.

Esango dugu erabaki-problema bat EXPTIME-osoa dela EXPTIMEn badago, eta EXPTIMEn dauden problema bakoitza murriztapen polinomial-denbora asko ditu. Jakina da arazo batzuk EXPTIME-osoak direla. P ≠ EXPTIME dela erakuts daitekeenez, arazo horiek P-tik kanpo daude, eta, beraz, denbora polinomioa baino gehiago behar dute. Izan ere, denbora-hierarkiaren teoremarako, ezin dira ebatzi esponentziala baino denbora nabarmen txikiagoan. Adibide batzuk N × N taula batean xake posizioetarako estrategia perfektua eta beste mahai jokoetarako antzeko arazoak aurkitzea dira.^[10]^[11]

Presburger aritmetikoan deklarazio baten egia erabakitzeko auziak are denbora gehiago eskatzen du. Fischer-ek eta Rabin-ek 1974an frogatu zuten n luzerako Presburger-en gutxienez c konstanteren baterako exekuzio-denbora $2^{2^{cn}}$ duela baieztapenen egia erabakitzen duen algoritmo bakoitzak. Beraz, badakigu problemak exekuzio-denbora esponentziala baino gehiago behar duela.^[12] Are zailagoak dira esan ezinezko arazoak, atxiloketaren auzia adibidez. Algoritmo mota horiek ezin dituzte guztiz ebatzi emandako arazoak, hau da, edozein algoritmo jakinetarako, gutxienez sarrera bat dago, eta algoritmo horrek ez du erantzun zuzena emango. Horrek esan nahi du erantzun okerra emango du, erantzun eztabaidaezinik eman gabe amaituko da, edo, bestela, betiko exekutatuko da, erantzunik eman gabe.

Beste problemak ere kontuan hartu ditzakegu, erabakitzeko problemak ez direnak adibidez. Klase horietako batek, arazoak kontatzean datzanak, #P du izena; NPko problema batek, "Ba al dago irtenbiderik? "galdetzen du, #P problemak berriz "Zenbat soluzio daude? " galdetzen du. Argi eta garbi, #P problema batek dagokion NP problema bezain zaila izan behar du gutxienez; izan ere, soluzioen zenbaketa batek berehala adierazten du gutxienez soluziorik badagoen, zenbaketa zero baino handiagoa den. Harrigarria bada ere, ustez zailak diren #P problema batzuk problema errazei dagozkie, hau da, P problemei (denbora lineala).^[13] Arazo horietarako, oso erraza da jakitea soluziorik badagoen, baina uste da oso zaila dela zenbat jakitea. Arazo horietako asko #P-osoa dira, eta, beraz, #P-n arazo zailenen artean; izan ere, horietako edozeini denbora polinomioa emanez gero, beste #P arazo guztiei denbora polinomioko soluzioa emango litzaieke.

P-k "erraza" esan nahi du?

Grafikoak exekuzio denbora vs. problemaren tamaina erakusten du artearen egoera bateko knapsack problema baterako, algoritmo espezializatua. Doikuntza koadratikoak problemaren konplexutasun algoritmikoa O((log(n))2) dela iradokitzen du.^[14]

Aurreko eztabaida guztiak P-k "erraza" esan nahi duela eta "ez P-n" "zaila"dela suposatu du, Cobhamen tesia bezala ezagutzen den suposizioa. Uste hori oso arrunta da konplexutasunaren teorian, baina badira salbuespenak.

Lehenik eta behin, suposizio hori gezurra izan daiteke praktikan. Algoritmo polinomio teoriko batek faktore edo berretzaile konstante oso handiak izan ditzake, eta ez da batere praktikoa. Adibidez, G grafiko batek H minor gisa duen ala ez erabakitzeko problema, non H finko dagoen, O(n²)-ren exekuzio-denbora batean ebatz daiteke, non n G-n erpin kopurua den. Hala ere, O notazio handiak H-ren superesponentzialki mendekoa den konstante bat ezkutatzen du. Konstantea handiagoa da $2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))$ baino (Knuth-ren goiko notazioa erabiliz h zenbakia da).^[15]^[16]

Bestalde, arazo bat NP-osoa dela frogatzen bada ere, eta P ≠ NP bada ere, praktikan arazoarentzako ikuspegi eraginkorrak egon daitezke. Algoritmoak daude NP-oso arazo askorentzat, hala nola knapsack-aren arazoa, saltzaile ibiltarien arazoa, eta boolearren satisfazioaren arazoa,arrazoizko denboran mundu errealeko kasu asko ezin hobeto konpon ditzakeena . Algoritmo horien batez besteko konplexutasun enpirikoa (denbora vs. problemaren tamaina) oso txikia izan daiteke. Adibide bat da programazio linealeko simplex algoritmoa, praktikan harrigarriro ondo funtzionatzen duena; kasuen denboran konplexutasun esponentziala izan arren, aldi berean exekutatzen da polinomial-denbora algoritmo ezagunenekin.

Azkenik, badira Turing-en makinaren eredura egokitzen ez diren kalkulu motak, non P eta NP definitzen diren, hala nola konputazio kuantikoa eta algoritmo aleatorizatuak. [[Kategoria:Ebatzi gabeko problema matematikoak]] [[Kategoria:Aieruak]]

Oharrak

↑ 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.

Erreferentziak

↑ 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..
↑ Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.
↑ William I. Gasarch. (June 2002). «The P=?NP poll.» SIGACT News 33 (2): 34–47. doi:10.1145/564585.564599..
↑ William I. Gasarch. «The Second P=?NP poll» SIGACT News 74.
↑ ^a ^b Guest Column: The Third P =? NP Poll1. .
↑ ^a ^b ^c ^d Arruabarrena Santos, Rosa. (1997). Algoritmika. UEU ISBN 978-84-86967-82-6. (kontsulta data: 2023-12-20).
↑ Aviezri Fraenkel and D. Lichtenstein. (1981). «Computing a perfect strategy for n × n chess requires time exponential in n» Journal of Combinatorial Theory in: Series A. 31 (2): 199–214. doi:10.1016/0097-3165(81)90016-9..
↑ David Eppstein. Computational Complexity of Games and Puzzles. .
↑ Fischer, Michael J.; Rabin, Michael O.. (1974). «Super-Exponential Complexity of Presburger Arithmetic» Proceedings of the SIAM-AMS Symposium in Applied Mathematics 7: 27–41..
↑ Valiant, Leslie G.. (1979). «The complexity of enumeration and reliability problems» SIAM Journal on Computing 8 (3): 410–421. doi:10.1137/0208032..
↑ Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark
↑ Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce. (2012). «The disjoint paths problem in quadratic time» Journal of Combinatorial Theory in: Series B. 102 (2): 424–435. doi:10.1016/j.jctb.2011.07.004..
↑ Johnson, David S.. (1987). «The NP-completeness column: An ongoing guide (edition 19)» Journal of Algorithms 8 (2): 285–303. doi:10.1016/0196-6774(87)90043-5..

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).

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

[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.

[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..

[6] Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.

[poll-7] William I. Gasarch. (June 2002). «The P=?NP poll.» SIGACT News 33 (2): 34–47. doi:10.1145/564585.564599..

[poll2-8] William I. Gasarch. «The Second P=?NP poll» SIGACT News 74.

[poll3-9] Guest Column: The Third P =? NP Poll1. .

[:0-10] Arruabarrena Santos, Rosa. (1997). Algoritmika. UEU ISBN 978-84-86967-82-6. (kontsulta data: 2023-12-20).

[Fraenkel1981-11] Aviezri Fraenkel and D. Lichtenstein. (1981). «Computing a perfect strategy for n × n chess requires time exponential in n» Journal of Combinatorial Theory in: Series A. 31 (2): 199–214. doi:10.1016/0097-3165(81)90016-9..

[12] David Eppstein. Computational Complexity of Games and Puzzles. .

[13] Fischer, Michael J.; Rabin, Michael O.. (1974). «Super-Exponential Complexity of Presburger Arithmetic» Proceedings of the SIAM-AMS Symposium in Applied Mathematics 7: 27–41..

[14] Valiant, Leslie G.. (1979). «The complexity of enumeration and reliability problems» SIAM Journal on Computing 8 (3): 410–421. doi:10.1137/0208032..

[Pisinger2003-15] Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark

[kkr12-16] Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce. (2012). «The disjoint paths problem in quadratic time» Journal of Combinatorial Theory in: Series B. 102 (2): 424–435. doi:10.1016/j.jctb.2011.07.004..

[17] Johnson, David S.. (1987). «The NP-completeness column: An ongoing guide (edition 19)» Journal of Algorithms 8 (2): 285–303. doi:10.1016/0196-6774(87)90043-5..

[oh 1]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]