NP (Konplexutasun klasea)

Konputazio-konplexutasunaren teorian, NP (nondeterministic polynomial time, "denboraldi polinomiko ez-determinista") erabaki-problemak sailkatzeko erabiltzen den konplexutasun-klase bat da. NP multzoa erabaki-problemen multzoa da; hau da, "bai" erantzuna duten instantziek froga bat dute, eta froga hori denbora polinomikoan egiazta daiteke makina determinista baten bidez. Bestela esanda, NP makina ez-determinista batek denbora polinomikoan ebatzi ditzakeen problemen multzoa da.

NP klasea

NP klasea erabaki-problemeen klase bat da, non proposatutako konponbide bat denbora polinomikoan egiaztatu daitekeen. Klase horren garrantzia bilaketa- eta optimizazio-arazo asko dituela da, non nolabaiteko ebazpena edo ebazpen ezagunak baina hobeak badauden jakin nahi da. Horien artean daude, adibidez, Saltzaile ibiltariaren problema (travelling salesman problem), zeinean galdetzen den grafo bateko erpin guztietatik pasatzen den ibilbide baten luzera emandako muga bat baino txikiagoa izan daitekeen, eta asetasun boolearraren problema (SAT), non jakin nahi den formula proposizional bat betetzen duen balioespen boolearrik badagoen.

NP klasearen garrantzia dela eta, ikerketa ugari egin dira NPko edozein problema denbora polinomikoan ebatziko lukeen algoritmo bat aurkitzeko. Hala ere, gaur egun ez da ezagutzen horrelakorik, eta uste da NP-osoko problemek ez dutela halako algoritmo eraginkorrik izango, salbu eta P = NP izango balitz.

NP-osoko lehen problema naturala asetasun boolearraren problema izan zen. Stephen Cookek 1971n frogatu zuen emaitza hori, eta Cooken teorema izena eman zitzaion. Cooken frogapena, alegia asetasuna NP-osokoa dela erakusten duena, nahiko konplexua da. Problema hori NP-osokoa dela ezarri ondoren, erraza bihurtu zen beste problema asko klase horretara murrizten zirela erakustea. Horrela, hasiera batean elkarren artean loturarik ez zuten problema askok egitura konputazional bera partekatzen dutela agerian geratu zen.

Definizio formala

NP konplexutasun-klasea, NTIME kontzeptuaren bidez defini daiteke honela:

${\displaystyle {\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k}),}$

non ${\displaystyle {\mathsf {NTIME}}(n^{k})}$, ${\displaystyle O(n^{k})}$ denboran Turing makina ez-determinista batek ebatzi ditzakeen erabaki problemen multzoa da.

Bestela esanda, NP Turing makina determinista egiaztatzaile gisa erabiliz ere defini daiteke. Hizkuntza bat L NP-n dago baldin eta soilik baldin p eta q polinomiak existitzen badira, eta Turing makina determinista bat M, non

• $x$ eta $y$ sarrera guztientzat, Turing makina determinista $M$-k denbora $p(|x|)$-tan exekutatzen du $(x,y)$ sarrerarekin.
• $x\in L$ denean, badago $q(|x|)$ luzerako y kate bat hala, non $M(x,y)=1.$
• $x\not \in L$ denean, eta $q(|x|)$ luzerako y kate guztientzat, $M(x,y)=0.$

Zergatik NP problema batzuk zailak dira kalkulatzeko

Klase honetan arazo garrantzitsu asko daudenez, ahalegin handiak egin dira NP-ko problemetarako denbora polinomikoko algoritmoak aurkitzeko. Hala ere, NP-n halako saiakerei aurre egiten dieten problema ugari daude oraindik, denbora super-polinomikoa behar dutela dirudielarik. Problema horiek denbora polinomikoan ez ote diren erabakigarriak, informatikako galdera ireki handienetako bat da (ikusi P versus NP ("P = NP") problema eztabaida sakon baterako).

Testuinguru honetan, NP-osoko erabaki-arazoen multzoa kontzeptu garrantzitsu bat da, NP-ren azpimultzo bat dena eta informalki NP-ko problema "gogorrenak" bezala deskribatu litekeena. Horietako batentzat ere denbora polinomikoko algoritmo bat badago, orduan NPko problema guztietarako denbora polinomikoko algoritmo bat dago. Hori dela eta, eta ikerketa dedikatuak huts egin duenez NP-osoa den edozein problemarentzako algoritmo polinomiko bat aurkitzean, behin problema bat NP-osoa dela frogatu denean, hau oso aintzat hartzen da problema honentzako algoritmo polinomiko bat nekez existituko den seinale gisa.

Hala ere, erabilera praktikoetan, baliabide konputazionalak soluzio optimo baten bila gastatu beharrean, soluzio nahiko ona (baina potentzialki suboptimoa) aurki daiteke askotan denbora polinomikoan. Halaber, problema batzuen bizitza errealeko aplikazioak errazagoak dira haien baliokide teorikoak baino.

Propietateak

NP itxita dago bilketan, ebakiduran, kateatzean, Kleene izarrean eta alderantzikatzean. Ez dakigu NP osagarrian itxita dagoen (galdera hau "NP versus co-NP" da).

Adibideak

Ziklo hamiltondarra

Grafo ez-zuzendu batean, zehaztu ezazu erpin bakoitza behin bakarrik bisitatzen duen ziklorik ba ote dagoen. Ziklo hautagai bat aurkezten bada, denbora polinomikoan baliozkotu daiteke, dagozkion ertz guztiak daudela eta erpin bakoitza behin agertzen dela egiaztatuz. Problema NP-osoa da, eta grafoen teoriaren eta konplexutasun konputazionalaren formulazio estandarretako bat da.

Grafo isomorfismoa

Grafoen isomorfismoaren problema da zehaztea ea bi grafo finitu egitura aldetik baliokideak diren, hau da, ertzak gordetzen dituen bi puntuen arteko bijekzio bat existitzen den. Problema NP klasekoa da, proposatutako korrespondentzia-funtzio oro denbora polinomikoan egiaztatu daitekeelako. Hala ere, ez dago argi problema P multzokoa den ala NP-osokoa den, eta konplexutasun-hierarkiaren erdibideko kokaleku batean dagoen arazo gisa hartzen da.

Subset sum

Subset Sum problemak, bere erabaki-formatuan, emandako osoko zenbaki multzo bat eta helburu-balio bat $T$ izanik, $T$ balioa zehazki ematen duen azpimultzorik badagoen galdetzen du. Proposatutako azpimultzo baten egiaztapena haren elementuak batuz egin daiteke denbora polinomikoan; horregatik, problema NP klasekoa da. Gainera, arazo hau NP-osokoa da bestelako arazo konbinatorioetatik egindako murrizketa klasikoen bidez.

Zenbaki osoen faktorizazioa

Zenbaki osoak faktorizatzeko problema honetan datza: $N$ zenbaki natural bat bere faktore lehenetan deskonposatzean edo zehaztutako propietate jakin batzuk betetzen dituen faktorizaziorik ba ote dagoen zehaztean. Proposatutako faktore multzo bat emanda, egiaztapena denbora polinomikoan egin daiteke, biderketaren bidez, eta, horregatik, problema NP-n dago. Ez dakigu NP-osoa den, ezta NP-hard ere murriztapen klasikoen pean, eta kriptografia algoritmikoan du garrantzi nagusia.