P ir NP problema: apibrėžimas, istorija ir reikšmė kompiuterių moksle

Pavyzdžiui, jei turite uždavinį ir kas nors sako: "Jūsų uždavinio atsakymas yra skaičių rinkinys 1, 2, 3, 4, 5", kompiuteris gali greitai nustatyti, ar atsakymas teisingas, ar klaidingas, tačiau gali prireikti labai daug laiko, kol kompiuteris pats sugalvos "1, 2, 3, 4, 5". Kitas pavyzdys - pirminių skaičių paieška. Lengva patikrinti, ar skaičius yra pirminis, tačiau labai sunku tokius skaičius rasti. Kai kuriems įdomiems, praktiniams tokio pobūdžio klausimams mums trūksta bet kokio būdo greitai surasti atsakymą, tačiau jei mums pateikiamas atsakymas, galima greitai patikrinti, t. y. patikrinti atsakymą. Tokiu būdu NP problemas galima laikyti panašiomis į mįsles: gali būti sunku sugalvoti atsakymą į mįslę, tačiau išgirdus atsakymą, jis atrodo akivaizdus. Šiame palyginime (analogijoje) pagrindinis klausimas yra toks: ar mįslės iš tikrųjų yra tokios sunkios, kaip mums atrodo, ar mes kažką praleidžiame?

Kadangi tokio pobūdžio P ir NP klausimai yra labai svarbūs praktiškai, daugelis matematikų, mokslininkų ir kompiuterių programuotojų nori įrodyti bendrą teiginį, kad kiekvienas greitai patikrinamas uždavinys taip pat gali būti greitai išspręstas. Šis klausimas yra pakankamai svarbus, kad Klaido matematikos institutas skirs 1 000 000 JAV dolerių tam, kas sėkmingai pateiks įrodymą arba tinkamą paaiškinimą, paneigiantį šį teiginį.

Giliau pažvelgę matome, kad visi P uždaviniai yra NP uždaviniai: sprendžiant uždavinį ir lyginant du sprendinius lengva patikrinti, ar sprendimas yra teisingas. Tačiau žmonės nori sužinoti apie priešingus dalykus: Ar yra kitų NP uždavinių, išskyrus P uždavinius, ar visi NP uždaviniai yra tik P uždaviniai? Jei NP uždaviniai iš tikrųjų nėra tokie patys kaip P uždaviniai (P ≠ NP), tai reikštų, kad jokių bendrų, greitų būdų tiems NP uždaviniams spręsti negali būti, kad ir kaip stropiai ieškotume. Tačiau jei visi NP uždaviniai yra P uždaviniai (P = NP), tai reikštų, kad egzistuoja nauji, labai greiti uždavinių sprendimo būdai. Tiesiog jų dar neradome.

Kadangi mokslininkų ir matematikų pastangomis kol kas nepavyko rasti bendrų, paprastų NP uždavinių sprendimo metodų, daugelis žmonių mano, kad yra kitų NP uždavinių nei P uždaviniai (t. y. kad P ≠ NP yra teisinga). Dauguma matematikų taip pat mano, kad tai tiesa, tačiau šiuo metu niekas to neįrodė griežta matematine analize. Jei pavyktų įrodyti, kad NP ir P yra tas pats (P = NP yra tiesa), tai turėtų didžiulę įtaką daugeliui kasdienio gyvenimo aspektų. Dėl šios priežasties P ir NP klausimas yra svarbi ir plačiai nagrinėjama tema.

Tarkime, kad kas nors nori pastatyti du bokštus, sudėdamas skirtingos masės akmenis. Norima įsitikinti, kad kiekvieno bokšto masė būtų lygiai tokia pati. Tai reiškia, kad akmenis reikės sudėti į dvi vienodos masės krūvas. Jei žmogus atspėtų, kaip, jo manymu, bus galima padalyti akmenis, būtų lengva patikrinti, ar jis buvo teisus. (Norint patikrinti atsakymą, galima padalyti akmenis į dvi krūvas, o tada svarstyklėmis patikrinti, ar jų masė vienoda.) Kadangi šį uždavinį, kurį kompiuterių mokslininkai vadina skirstymo uždaviniu, lengva patikrinti - kaip pamatysime, lengviau nei jį išspręsti - jis nėra P uždavinys. ^[]

Kaip sunku jį išspręsti, atvirai? Jei pradėsime nuo 100 akmenų, yra 2^{100-1}-1 = 633 825 300 114 700 748 351 602 687, arba maždaug 6,3 x 10^{29} galimų būdų (kombinacijų) padalyti šiuos akmenis į dvi krūvas. Jei kasdien būtų galima patikrinti vieną unikalų akmenų derinį, prireiktų 1,3 x 10^{22} arba 1 300 000 000 000 000 000 000 000 000 000 metų pastangų. Palyginimui, fizikai mano, kad Visatos amžius yra maždaug 1,4 x 10^{10} metų (450 000 000 000 000 000 000 000 arba maždaug 4,5 x 10^{17} sekundžių, t. y. maždaug viena trilijoninė dalis laiko, kurio prireiktų mūsų pastangoms sudėlioti akmenų krūvas. Tai reiškia, kad jei imtume visą laiką, kuris praėjo nuo Visatos pradžios, norint patikrinti visus skirtingus uolienų dalijimo būdus, kiekvieną sekundę reikėtų patikrinti daugiau nei du trilijonus (2 000 000 000 000 000) skirtingų uolienų dalijimo būdų.

Jei galingas kompiuteris būtų užprogramuotas išbandyti visus šiuos uolienų padalijimo būdus, dabartinėmis sistemomis būtų galima patikrinti 1 000 000 {\displaystyle 1 000 000} kombinacijų per sekundę. Tai reiškia, kad norint patikrinti visus uolienų padalijimo būdus, reikėtų 2 000 000 000 {\displaystyle 2 000 000} labai galingų kompiuterių, veikiančių nuo pat visatos atsiradimo.

Tačiau gali būti įmanoma rasti būdą, kaip padalyti uolienas į dvi lygias krūvas netikrinant visų derinių. Klausimas "Ar P yra lygus NP?" yra trumpinys, kuriuo klausiama, ar gali egzistuoti koks nors toks metodas.

Yra daug svarbių NP problemų, kurių žmonės nežino, kaip išspręsti greičiau nei išbandyti visus įmanomus atsakymus. Štai keletas pavyzdžių:

• Keliaujantis pardavėjas nori aplankyti 100 miestų važiuodamas automobiliu, kelionę pradėdamas ir baigdamas namuose. Jis turi ribotas benzino atsargas, todėl iš viso gali nuvažiuoti tik 10 000 km. Jis nori sužinoti, ar galės aplankyti visus miestus, nepritrūkęs benzino.
• Mokykloje yra 100 skirtingų klasių, o mokytojas turi pasirinkti po vieną valandą kiekvienos klasės baigiamajam egzaminui. Kad būtų išvengta sukčiavimo, visi klasėje besimokantys mokiniai tos klasės egzaminą turi laikyti tuo pačiu metu. Jei mokinys lanko daugiau nei vieną klasę, visų tų klasių egzaminai turi vykti skirtingu laiku. Mokytojas nori sužinoti, ar jis gali suplanuoti visus egzaminus tą pačią dieną, kad kiekvienas mokinys galėtų laikyti kiekvienos klasės egzaminą.
• Ūkininkas nori į rinką nuvežti 100 skirtingos masės arbūzų. Jai reikia supakuoti arbūzus į dėžes. Į kiekvieną dėžę galima sutalpinti tik 20 kilogramų nesulūžus. Ūkininkė nori sužinoti, ar jai užteks 10 dėžių visiems 100 arbūzų nuvežti į rinką. (Tai trivialu, jei ne daugiau kaip vienas arbūzas sveria daugiau kaip 2 kg, tai į kiekvieną dėžę galima įdėti bet kuriuos 10 arbūzų, jei ne daugiau kaip dešimt arbūzų sveria daugiau kaip 2 kg, tai į kiekvieną dėžę galima įdėti po vieną ir t. t. Greitas sprendimas; stebėjimas bus raktas į bet kokį greitą sprendimą, pavyzdžiui, šį ar skaičių aibės uždavinį).
• Didelėje meno galerijoje yra daugybė kambarių, o ant kiekvienos sienos kabo daug brangių paveikslų. Galerijos savininkas nori nusipirkti kameras paveikslams stebėti, jei vagis bandytų kurį nors iš jų pavogti. Jis nori sužinoti, ar užteks 100 kamerų, kad kiekvienas paveikslas būtų matomas bent viena kamera.
• Klika problema: mokyklos direktorius turi sąrašą, kuriame nurodyta, kurie mokiniai draugauja tarpusavyje. Ji nori rasti 10 % mokinių grupę, kurioje visi mokiniai draugauja tarpusavyje.

Pateiktame pavyzdyje matome, kad esant 100 {\displaystyle 100} akmenų, yra 2 100 {\displaystyle 2^{100}} būdų padalyti akmenų aibę. Jei turime n {\displaystyle n} akmenų, yra 2 n {\displaystyle 2^{n}} derinių. Funkcija f ( n ) = 2 n {\displaystyle f(n)=2^{n}} yra eksponentinė funkcija. Ji svarbi NP, nes modeliuoja blogiausiu atveju reikalingų skaičiavimų, reikalingų uždaviniui išspręsti, skaičių, taigi ir blogiausiu atveju reikalingą laiką.

Iki šiol sudėtingiems uždaviniams spręsti reikėjo 2 n {\displaystyle 2^{n}} skaičiavimų. Bet kuriai konkrečiai problemai spręsti žmonės rado būdų, kaip sumažinti reikalingų skaičiavimų skaičių. Galima sugalvoti būdą, kaip atlikti tik 1 % skaičiavimų skaičiaus blogiausiu atveju ir taip sutaupyti daug skaičiavimų, tačiau tai vis tiek yra 0,01 × ( 2 n ) {\displaystyle 0,01\ kartus (2^{n})} skaičiavimų. O kiekviena papildoma uola vis tiek padvigubina skaičiavimų, reikalingų uždaviniui išspręsti, skaičių. Yra įžvalgų, kurios gali padėti sukurti metodus, leidžiančius atlikti dar mažiau skaičiavimų, kuriant modelio variantus: pvz., 2 n / n 3 {\displaystyle 2^{n}/n^{3}}. . Tačiau didėjant n {\displaystyle n} vis tiek dominuoja eksponentinė funkcija.

Panagrinėkime egzaminų tvarkaraščio sudarymo problemą (aprašyta pirmiau). Tarkime, kad yra 15 000 mokinių. Yra kompiuterinė programa, kuri sudaro visų 15000 mokinių tvarkaraščius. Ji paleidžiama per valandą ir pateikia egzaminų tvarkaraštį taip, kad visi mokiniai galėtų laikyti egzaminus per vieną savaitę. Ji atitinka daugybę taisyklių (jokių egzaminų, vykstančių vienas po kito, ne daugiau kaip 2 egzaminai per 28 valandas, ...), kad sumažintų egzaminų savaitės stresą. Programa veikia vieną valandą per pusmečio pertrauką ir kiekvienas žino savo egzaminų tvarkaraštį, turėdamas pakankamai laiko pasiruošti.

Tačiau kitais metais mokinių padaugėjo 10. Jei ta pati programa veikia tame pačiame kompiuteryje, ta viena valanda taps 2 10 {\displaystyle 2^{10}} valandų, nes kiekvienas papildomas mokinys padvigubina skaičiavimus. Tai 6 {\displaystyle 6} savaitės! Jei būtų dar 20 mokinių, tada

2 20 {\displaystyle 2^{20}} valandų = 1048576 {\displaystyle 1048576}valandų ~ 43691 {\displaystyle 43691} dienų ~ 113 {\displaystyle 113} metų

Taigi 15000 {\displaystyle 15000} mokinių reikia vienos valandos. 15020 {\displaystyle 15020} mokinių tai trunka 113 {\displaystyle 113} metų.

Kaip matote, eksponentinės funkcijos auga labai greitai. Dauguma matematikų mano, kad sunkiausiems NP uždaviniams išspręsti reikia eksponentinio laiko.

Matematikai gali įrodyti, kad kai kurie NP uždaviniai yra NP-užbaigti. NP-užbaigtą uždavinį yra bent jau taip pat sunku išspręsti, kaip ir bet kurį kitą NP uždavinį. Tai reiškia, kad jei kas nors rastų metodą, kaip greitai išspręsti bet kurį NP-komplektinį uždavinį, tą patį metodą galėtų panaudoti kiekvienam NP uždaviniui greitai išspręsti. Visi pirmiau išvardyti uždaviniai yra NP-išsamūs, todėl jei pardavėjas rado būdą, kaip greitai suplanuoti kelionę, jis galėtų apie tai pasakyti mokytojai, o ji galėtų panaudoti tą patį metodą egzaminams suplanuoti. Ūkininkas galėtų tuo pačiu metodu nustatyti, kiek dėžių jam reikia, o moteris galėtų tuo pačiu metodu rasti būdą, kaip pastatyti savo bokštus.

Kadangi metodas, kuris greitai išsprendžia vieną iš šių problemų, gali išspręsti visas, yra daug žmonių, kurie nori jį rasti. Tačiau kadangi yra labai daug skirtingų NP-užbaigtų uždavinių ir niekas iki šiol nerado būdo, kaip greitai išspręsti bent vieną iš jų, dauguma ekspertų mano, kad greitai išspręsti NP-užbaigtų uždavinių neįmanoma.

Pagrindinės savybės

Skaičiavimo sudėtingumo teorijoje sudėtingumo klasė NP-užbaigtumas (sutrumpintai NP-C arba NPC) - tai problemų klasė, kuriai būdingos dvi savybės:

• Jis priklauso NP (nedeterministinių polinominio laiko uždavinių) aibei: Bet kurį duotą uždavinio sprendimą galima greitai (per polinominį laiką) patikrinti.
• Jis taip pat yra NP sunkiai sprendžiamų uždavinių aibėje: Tai yra sunkiausių NP uždavinių aibė. NP sunkūs uždaviniai nebūtinai turi būti NP elementai; iš tiesų jie gali būti net neišsprendžiami.

Oficiali apžvalga

NP-užbaigtumas yra NP poaibis, visų sprendimų uždavinių, kurių sprendimus galima patikrinti per polinominį laiką, aibė; NP galima lygiavertiškai apibrėžti kaip sprendimų uždavinių, kuriuos mašina išsprendžia per polinominį laiką, aibę. NP uždavinys p taip pat yra NPC tada ir tik tada, kai kiekvienas kitas NP uždavinys yra transformuojamas į p per polinominį laiką. NP-užbaigtas turėjo būti vartojamas kaip būdvardis: NP klasės uždaviniai buvo kaip NP+užbaigti uždaviniai.

NP-užbaigti uždaviniai tiriami, nes atrodo, kad gebėjimas greitai patikrinti uždavinio sprendimus (NP) koreliuoja su gebėjimu greitai išspręsti uždavinį (P). Nustatyta, kad kiekvienas NP uždavinys yra greitai išsprendžiamas - jis vadinamas P = NP: uždavinių aibe. Vienintelis NP uždavinys išsprendžiamas greitai, greičiau nei kiekvienas NP uždavinys taip pat greitai išsprendžiamas, nes NP uždavinio apibrėžimas teigia, kad kiekvienas NP uždavinys turi būti greitai redukuojamas į kiekvieną NP uždavinį (jis redukuojamas per polinominį laiką). [1]

Pavyzdžiai

Yra žinoma, kad loginis patenkinamumo uždavinys yra NP pilnas. 1972 m. Richardas Karpas suformulavo 21 uždavinį, kurie yra žinomi kaip NP-užbaigti. Jos žinomos kaip 21 Karpo NP-užbaigtumo uždavinys. Tarp jų yra tokie uždaviniai kaip sveikųjų skaičių programavimo uždavinys, kuriame taikomi tiesinio programavimo metodai sveikiesiems skaičiams, kuprinės uždavinys arba viršūnių padengimo uždavinys.