P proti NP (P vs NP): definicija, zgodovina in pomen v računalništvu

Pojasnila

Če imate na primer problem in nekdo reče: "Odgovor na vaš problem je niz števil 1, 2, 3, 4, 5", lahko računalnik hitro ugotovi, ali je odgovor pravilen ali napačen, vendar pa lahko traja zelo dolgo, preden računalnik sam pride do odgovora "1, 2, 3, 4, 5". Drug primer je iskanje praštevil. Enostavno je preveriti, ali je število praštevilo, vendar je zelo težko ta števila sploh najti. Pri nekaterih zanimivih, praktičnih vprašanjih te vrste nimamo nobenega načina za hitro iskanje odgovora, če pa nam je odgovor na voljo, je mogoče odgovor hitro preveriti - torej preveriti. Na ta način si lahko probleme NP predstavljamo kot uganke: morda je težko najti odgovor na uganko, toda ko enkrat slišimo odgovor, se nam ta zdi očiten. Pri tej primerjavi (analogiji) je osnovno vprašanje: ali so uganke res tako težke, kot mislimo, da so, ali pa nam kaj uide?

Ker so tovrstna vprašanja P proti NP praktično tako pomembna, želijo številni matematiki, znanstveniki in računalniški programerji dokazati splošno trditev, da je mogoče vsak hitro preverjen problem tudi hitro rešiti. To vprašanje je dovolj pomembno, da bo Clayjev matematični inštitut dal 1.000.000 dolarjev vsakomur, ki bo uspešno predložil dokaz ali veljavno razlago, ki ga bo ovrgla.

Če se nekoliko poglobimo, vidimo, da so vsi problemi P problemi NP: da je rešitev pravilna, lahko preverimo tako, da rešimo problem in primerjamo obe rešitvi. Vendar pa ljudje želijo vedeti tudi nasprotno: Ali obstajajo še kakšni drugi NP problemi, ki niso P problemi, ali pa so vsi NP problemi samo P problemi? Če problemi NP res niso enaki problemom P (P ≠ NP), bi to pomenilo, da splošnih, hitrih načinov za reševanje teh problemov NP ne more biti, ne glede na to, kako zelo se trudimo. Če pa so vsi NP problemi P problemi (P = NP), bi to pomenilo, da nove, zelo hitre metode reševanja problemov obstajajo. Le da jih še nismo našli.

Ker znanstveniki in matematiki po svojih najboljših močeh še niso našli splošnih in enostavnih metod za reševanje NP-problemov, mnogi verjamejo, da obstajajo NP-problemi, ki niso P-problemi (to pomeni, da je P ≠ NP resničen). Tudi večina matematikov verjame, da je to res, vendar tega trenutno še nihče ni dokazal s strogo matematično analizo. Če bi lahko dokazali, da sta NP in P enaka (P = NP je resničen), bi to imelo velik vpliv na številne vidike vsakdanjega življenja. Zato je vprašanje P proti NP pomembna in široko preučevana tema.

Primer

Recimo, da želi nekdo zgraditi dva stolpa, tako da zloži kamne različnih mas. Nekdo želi zagotoviti, da ima vsak od stolpov popolnoma enako maso. To pomeni, da bo moral kamne zložiti na dva kupa, ki imata enako maso. Če uganemo delitev kamnov, za katero menimo, da bo ustrezala, bomo zlahka preverili, ali smo imeli prav. (Odgovor lahko preverimo tako, da kamne razdelimo na dva kupa, nato pa s tehtnico preverimo, ali imajo enako maso.) Ker je ta problem, ki ga računalničarji imenujejo "delitev", enostavno preveriti - lažje kot ga rešiti, kot bomo videli -, to ni problem P. ^[]

Kako težko ga je rešiti? Če začnemo s samo 100 kamni, obstaja 2^{100-1}-1 = 633.825.300.114.114.700.748.351.602.687 ali približno 6,3 x 10^{29} možnih načinov (kombinacij) za razdelitev teh kamnov na dva kupa. Če bi lahko vsak dan preverili eno edinstveno kombinacijo kamnov, bi za to potrebovali 1,3 x 10^{22} ali 1 300 000 000 000 000 000 000 000 let truda. Za primerjavo: fiziki menijo, da je vesolje staro približno 1,4 x 10^{10} let (450 000 000 000 000 000 000 000 ali približno 4,5 x 10^{17} sekund oziroma približno eno trilijoninko toliko časa, kot bi ga potrebovali za naš napor pri polaganju kamnov na kup. To pomeni, da bi morali, če vzamemo ves čas, ki je pretekel od začetka vesolja, vsako sekundo preveriti več kot dva bilijona (2.000.000.000.000.000) različnih načinov deljenja kamnin, da bi preverili vse različne načine.

Če bi programirali zmogljiv računalnik, ki bi preizkusil vse te načine delitve kamnin, bi lahko s sedanjimi sistemi preverili , 1, 000{\displaystyle000 1.000.000} kombinacij na sekundo. To pomeni, da bi še vedno potrebovali , 2, 000{\displaystyle000 2.000.000} zelo zmogljivih računalnikov, ki bi delovali že od nastanka vesolja, da bi preizkusili vse načine delitve kamnin.

Morda pa je mogoče najti način, kako kamenje razdeliti na dva enaka kupa, ne da bi preverili vse kombinacije. Vprašanje "Ali je P enako NP?" je okrajšava za vprašanje, ali takšna metoda lahko obstaja.

Zakaj je to pomembno

Obstaja veliko pomembnih problemov NP, ki jih ljudje ne znajo rešiti na način, ki bi bil hitrejši od testiranja vseh možnih odgovorov. Tukaj je nekaj primerov:

• Potujoči prodajalec želi z vožnjo obiskati 100 mest, potovanje pa začeti in končati doma. Ker ima omejene zaloge bencina, lahko prevozi le 10.000 kilometrov. Zanima ga, ali lahko obišče vsa mesta, ne da bi mu zmanjkalo bencina.
• Šola ima 100 različnih razredov, učitelj pa mora izbrati eno uro za zaključni izpit vsakega razreda. Da bi preprečili goljufanje, morajo vsi učenci, ki obiskujejo razred, opravljati izpit za ta razred ob isti uri. Če učenec obiskuje več razredov, morajo biti vsi izpiti ob različnih urah. Učitelj želi vedeti, ali lahko vse izpite razpiše na isti dan, tako da bo vsak učenec lahko opravljal izpit za vsak svoj razred.
• Kmet želi na trg pripeljati 100 lubenic različnih mas. Lubenice mora zapakirati v škatle. V vsako škatlo lahko spravi le 20 kilogramov, ne da bi se razbila. Kmet mora vedeti, ali bo 10 škatel zadoščalo, da bo na trg odnesel vseh 100 lubenic. (To je trivialno, če največ ena lubenica tehta več kot 2 kg, potem jih lahko v vsak zaboj damo poljubnih 10, če največ deset lubenic tehta več kot 2 kg, potem lahko v vsak zaboj damo po eno itd. do hitre rešitve; opazovanje bo ključ do vsake hitre rešitve, kot je ta ali problem množice števil).
• V veliki umetniški galeriji je veliko sob, vsaka stena pa je prekrita s številnimi dragimi slikami. Lastnik galerije želi kupiti kamere, s katerimi bi opazoval te slike, če bi kateri od tatov skušal katero od njih ukrasti. Zanima ga, ali bo dovolj 100 kamer, da bo vsako sliko lahko videla vsaj ena kamera.
• Problem klike: ravnatelj šole ima seznam učencev, ki so med seboj prijatelji. Želi najti skupino 10 % učencev, ki so vsi prijatelji drug z drugim.

Eksponentni čas

V zgornjem primeru vidimo, da je pri {\displaystyle100 100} kamnov {\displaystyle2100 2^{100}} načinov razdelitve množice kamnov. Pri n {\displaystyle n} skalah obstaja n2 {\displaystyle 2^{n}} kombinacij. Funkcija f ( n ) = n 2{\displaystyle f(n)=2^{n}} je eksponentna funkcija. Za NP je pomembna, ker modelira najslabše možno število izračunov, ki so potrebni za rešitev problema, in s tem najslabše možno količino potrebnega časa.

Doslej so rešitve za težke probleme zahtevale n 2{\displaystyle 2^{n}} izračunov. Za vsak posamezen problem so ljudje našli načine, kako zmanjšati število potrebnih izračunov. Nekdo lahko ugotovi, da je mogoče narediti le 1 % najslabšega možnega števila izračunov, kar prihrani veliko računanja, vendar je to še vedno ×0.01 ( n2 ) {\displaystyle 0,01\krat (2^{n})} izračunov. In vsaka dodatna skala še vedno podvoji število izračunov, potrebnih za rešitev problema. Obstajajo spoznanja, ki lahko ustvarijo metode za še manjše število izračunov, ki proizvajajo različice modela: npr. n 2/ n {\displaystyle 2^{n}/n^{3}}3 . Vendar eksponentna funkcija še vedno prevladuje, ko n {\displaystyle n} narašča.

Razmislite o problemu razporejanja izpitov (opisano zgoraj). Nato predpostavimo, da je študentov 15.000. Obstaja računalniški program, ki upošteva urnike vseh 15000 študentov. Izvede se v eni uri in izdela razpored izpitov tako, da lahko vsi študenti opravijo izpite v enem tednu. Upošteva številna pravila (nobenih izpitov zapored, največ dva izpita v 28 urah ...), da bi omejil stres izpitnega tedna. Program se izvaja eno uro ob vmesnem odmoru in vsi poznajo svoj urnik izpitov ter imajo dovolj časa za pripravo.

Naslednje leto pa je v šoli 10 učencev več. Če isti program teče na istem računalniku, se bo ena ura spremenila v {\displaystyle210 2^{10}} ur, saj vsak dodatni učenec podvoji računanje. To je {\displaystyle6 6} tednov! Če bi bilo še 20 učencev, potem bi

220  {\displaystyle 2^{20}} ur = {\displaystyle1048576 1048576} ur ~ {\displaystyle43691 43691} dni ~ {\displaystyle113 113} let

Tako za {\displaystyle15000 15000} učencev traja eno uro. Za {\displaystyle15020 15020} učencev traja {\displaystyle113 113} let.

Kot lahko vidite, eksponentne funkcije rastejo zelo hitro. Večina matematikov meni, da najtežji problemi NP za rešitev potrebujejo eksponentni čas.

NP-popolni problemi

Matematiki lahko dokažejo, da obstajajo nekateri problemi NP, ki so NP-popolni. Problem NP-kompleta je vsaj tako težko rešljiv kot kateri koli drug problem NP. To pomeni, da če bi nekdo našel metodo za hitro reševanje katerega koli NP-skupnega problema, bi lahko isto metodo uporabil za hitro reševanje vsakega NP-problema. Vsi zgoraj našteti problemi so NP-popolni, zato bi lahko prodajalec, če bi našel način za hitro načrtovanje potovanja, to povedal učiteljici in ta bi lahko isto metodo uporabila za načrtovanje izpitov. Kmet bi lahko z isto metodo določil, koliko škatel potrebuje, ženska pa bi lahko z isto metodo našla način za gradnjo stolpov.

Ker lahko metoda, ki hitro reši enega od teh problemov, reši vse, si jo želi najti veliko ljudi. Ker pa je toliko različnih problemov NP-Complete in ker nihče do zdaj ni našel načina za hitro rešitev niti enega od njih, večina strokovnjakov meni, da hitro reševanje problemov NP-Complete ni mogoče.

Osnovne lastnosti

V teoriji računske zahtevnosti je razred zahtevnosti NP-kompleten (skrajšano NP-C ali NPC) razred problemov, ki ima dve lastnosti:

• Je v množici problemov NP (nedeterministični polinomski čas): Vsako rešitev problema je mogoče preveriti hitro (v polinomskem času).
• Prav tako je v naboru NP-težkih problemov: Ti so vsaj tako težki kot najtežji problemi v NP. Ni nujno, da so problemi, ki so NP-težki, elementi NP; morda celo niso rešljivi.

Formalni pregled

NP-kompleten je podmnožica NP, množice vseh odločitvenih problemov, katerih rešitve je mogoče preveriti v polinomskem času; NP lahko enakovredno opredelimo kot množico odločitvenih problemov, ki jih na stroju rešimo v polinomskem času. Problem p v NP je tudi v NPC, če in samo če se vsak drug problem v NP pretvori v p v polinomskem času. NP-polni naj bi se uporabljal kot pridevnik: problemi v razredu NP-polni so bili kot NP+polni problemi.

Probleme z NP-kompletom preučujemo, ker se zdi, da je sposobnost hitrega preverjanja rešitev problema (NP) povezana s sposobnostjo hitrega reševanja problema (P). Ugotovljeno je bilo, da je vsak problem v NP hitro rešen - kot se imenuje množica problemov P = NP:. Posamezen problem v NP-kompletu je rešen hitro, hitreje kot vsak problem v NP, ki je prav tako hitro rešen, saj definicija problema v NP-kompletu pravi, da mora biti vsak problem v NP hitro reduktibilen na vsak problem v NP-kompletu (reducira se v polinomskem času). [1]

Primeri

Znano je, da je problem Boolove zadovoljivosti NP popoln. Leta 1972 je Richard Karp oblikoval 21 problemov, za katere je znano, da so NP-popolni. Ti problemi so znani kot 21 Karpovih NP-popolnih problemov. Med njimi so problemi, kot so problem celoštevilskega programiranja, ki uporablja tehnike linearnega programiranja za cela števila, problem knapsack ali problem pokritja vrhov.