P-NP problema yra matematikos ir kompiuterių mokslo iššūkis, tačiau ar ji gali būti raktas į sudėtingų realaus pasaulio problemų sprendimą?
Kuprinės problema ir P-NP galvosūkis
Vagis įeina į juvelyrinių dirbinių parduotuvę, apsižvalgo ir trumpai susimąsto. „Kad ir kaip norėčiau su savimi pasiimti visus papuošalus, mano krepšys turi ribotą svorį. Kokiais brangakmeniais turėčiau užpildyti maišelį, kad gaučiau daugiausia pinigų? Krepšyje yra per daug galimų brangakmenių derinių, kad būtų galima apskaičiuoti jų vertę. Jei skaičiuoti rankomis per daug laiko, galite pagalvoti apie pažangiausių kompiuterių ir programinės įrangos su geriausiais algoritmais naudojimą. Deja, šiuo metu nėra algoritmo, kuris greitai išspręstų šią problemą. Net ir naudojant galingiausius kompiuterius, tai užtruktų tūkstančius ar daugiau metų. Priežastis, kodėl ši problema, vadinama „kupinės problema“, yra tokia sudėtinga, yra ta, kad ji panaši į P-NP problemą, kuri tik 53 % matematikų tiki, kad bus išspręsta iki 2100 m.
P-NP problema yra vienas iš septynių geriausių pasaulio matematikos iššūkių. JAV Clay matematikos institutas išvardijo septynias neišspręstas XXI amžiaus matematikos problemas ir už kiekvieną pasiūlė po 21 milijoną dolerių. Tik Puankarės spėjimas buvo įrodytas, tačiau kiti šeši, įskaitant P-NP problemą, lieka neišspręsti ir daugelio matematikų ginčijami. Daugelis optimizavimo problemų įvairiose visuomenės srityse, įskaitant vagies pavyzdį, yra „sunkios problemos“, turinčios didelį skaičiavimo sudėtingumą. P-NP problema yra įrodyti, ar yra lengvas būdas išspręsti šias „sunkias problemas“.
Kas yra skaičiavimo sudėtingumas?
Skaičiavimo sudėtingumas yra objektyvus problemos, kurią bandome išspręsti, matas. Šiame kontekste kietumas nereiškia, kad nėra problemos sprendimo, o tai, kad nėra algoritmo, kuris galėtų greitai išspręsti problemą.
Štai paprastas pavyzdys. Yra 100 rutuliukų, ant kurių užrašyti skirtingi atsitiktiniai skaičiai.
– 1 uždavinys: kokia didžiausia ant rutuliukų užrašytų skaičių reikšmė?
– 2 uždavinys: ar yra rutuliukų rinkinys, kuriame ant rutuliukų užrašytų skaičių suma yra 100?
1 užduotyje, jei išimsite vieną rutulį ir pakeisite jį, kai jo skaičius didesnis nei tas, kurį laikote, skaičius yra didžiausias, o tai reiškia, kad iš viso reikia atlikti 99 palyginimus. Palyginimui, 2 uždaviniui reikia patikrinti, ar yra aibė, kurios suma yra 100 kiekvienai kombinacijai, kurią galima sudaryti su 100 rutuliukų, o tai reiškia, kad blogiausiu atveju turime atlikti maždaug nuo 2 iki 100 laipsnio (* bendras poaibių skaičius). Tai neįsivaizduojamai ilgas laikas, apie 23 kvadrilijonus metų, net jei darytume prielaidą, kad superkompiuteris atlieka kvadrilijoną operacijų per sekundę.
Algoritmas vadinamas daugianario laiko algoritmu, jei, didėjant rutuliukų (N) skaičiui, operacijų skaičius (N-1) neviršija rutuliukų skaičiaus daugianario funkcijos, kaip 1 uždavinio sprendime. Tokio algoritmo buvimas gali būti skirtumas tarp lengvos ir sunkios problemos.
P=NP?
Atkreipkite dėmesį, kad norint rasti atsakymą į 2 sudėtingą uždavinį, kuriam nėra polinominio laiko algoritmo, reikia daug skaičiavimų, tačiau patikrinti, ar atsakymas teisingas, yra labai paprasta. Turint omenyje rutulių rinkinį, turėtų užtrukti mažiau nei 10 sekundžių patikrinti, ar užrašytų skaičių suma yra 100. Kitaip tariant, vien todėl, kad problemą lengva apskaičiuoti, dar nereiškia, kad yra paprastas būdas ją išspręsti. . Ar yra paprastas būdas tai išspręsti, o matematikai jo dar nerado, ar nėra lengvo būdo tai išspręsti, dar reikia pamatyti. Tai yra P-NP problema.
P rinkinys yra paprastų uždavinių, į kuriuos galima atsakyti daugianario laiku, rinkinys, pvz., 1 uždavinys, o NP rinkinys yra uždavinių, kurių teisingumą galima patikrinti daugianario laiku, rinkinys. P-NP problema yra uždavinys įrodyti, ar P aibė ir NP aibė yra lygiavertės aibės. Savaime aišku, kad P rinkinys priklauso NP rinkiniui. Tačiau dar neįrodyta, kad kiekviena NP rinkinio problema yra P rinkinyje. Jei tai įrodoma, tai reiškia, kad kiekviena lengvai apskaičiuojama problema turi lengvai užbaigiamą sprendimą, ty mums nebereikia 10^28 metų 2 uždaviniui išspręsti.
NP problemos ir realus gyvenimas
Tai ne tik matematinis P-NP uždavinio sunkumas, todėl jis yra vienas iš septynių geriausių visų laikų matematikos uždavinių. Priežastis, kurią taip svarbu įrodyti, yra ta, kad tai glaudžiai susiję su realaus pasaulio problemų sprendimu. Realaus pasaulio problemos tokiose įvairiose pramonės šakose kaip lėktuvų planavimas, puslaidininkių projektavimas, gręžimo mašinų išdėstymas, genominių duomenų analizė, astronominio teleskopo išdėstymas ir rentgeno kristalografija yra NP sudėtingos problemos, kurias išspręsti reikia ilgai. Tačiau mes dar turime atrasti algoritmą, kaip greitai priimti optimalius sprendimus, ir net nežinome, ar toks algoritmas egzistuoja. Taigi, jei nėra daugianario laiko algoritmo, kaip šiuo metu priimame sprendimus dėl realaus pasaulio problemų?
Įvairių sričių, tokių kaip matematika, informatika, pramonės inžinerija ir kt., mokslininkai tiria ir kuria įvairius apytikslius sprendimus, kurie apytiksliai atitinka optimalų sprendimą realaus pasaulio problemoms spręsti. Dar kartą apsvarstykite vagies problemą: jei optimalaus brangakmenių derinio paieška užtruktų ilgai, alternatyva – rasti būdą, kaip greitai ir efektyviai priimti sprendimus su palyginti nedideliu pelnu. Vienas iš būdų tai padaryti gali būti apskaičiuoti kiekvieno brangakmenio svorį ir pirmiausia užpildyti savo krepšį brangakmeniais, kurių svorio vertė yra didžiausia. Tai apytikslis sprendimas, vadinamas gobšiąja euristika, kuri buvo praktiškai panaudota, kai reikia greitai priimti sprendimus. Nors šie apytiksliai skaičiavimai nėra optimalūs, jie labai padeda priimti sprendimus realaus pasaulio problemomis, turinčiomis laiko apribojimus. Be to, kai kurie apytiksliai sprendimai tampa sudėtingesni, kai kuriais apytiksliais skaičiavimais galima apytiksliai nustatyti optimalią konkrečios problemos vertę 0.5 % paklaida.
Saugumo pramonė ir NP problemos
Priešingai nei pirmiau minėtos pramonės šakos, yra viena pramonės šaka, kuri nenori, kad būtų rastas lengvas algoritmas NP problemoms išspręsti. Tai saugumo pramonė. Dabartinės saugumo schemos yra organizuotos taip, kad NP problema būtų naudojama atvirkščiai. Jei žinote slaptažodį, nesunku įsitikinti, kad tai tinkamas slaptažodis, bet nelengva jį rasti, nes nėra daugianario laiko algoritmo, kaip jį rasti. Galbūt visa saugumo pramonė tikisi, kad P-NP problema išliks amžina mįslė.
Net jei P = NP įrodyta, tai nereiškia, kad visos NP problemos yra lengvai išsprendžiamos. Tačiau akivaizdu, kad daugianario laiko algoritmo egzistavimas paskatins daugelį tyrėjų tirti daugianario laiko algoritmus sunkioms NP problemoms spręsti. Tai turės didelį poveikį efektyvumo gerinimui ir realių problemų optimizavimui. Ir atvirkščiai, jei paaiškėja, kad P≠NP, tai reiškia, kad tokio metodo nėra, o tai reiškia, kad daugelis NP problemų išliks neišsprendžiamos realiame pasaulyje. Bet kuriuo atveju bus įdomu pamatyti, koks bus šios galvosūkio rezultatas.
