P verzus NP

Napríklad, ak máte problém a niekto povie: "Odpoveďou na váš problém je množina čísel 1, 2, 3, 4, 5", počítač môže byť schopný rýchlo zistiť, či je odpoveď správna alebo nesprávna, ale môže trvať veľmi dlho, kým počítač skutočne sám príde na "1, 2, 3, 4, 5". Ďalším príkladom je hľadanie prvočísel. Je ľahké skontrolovať, či je číslo prvočíslo, ale je veľmi ťažké tieto čísla vôbec nájsť. Pri niektorých zaujímavých praktických otázkach tohto druhu nám chýba akýkoľvek spôsob, ako rýchlo nájsť odpoveď, ale ak máme k dispozícii odpoveď, je možné si ju rýchlo overiť - teda overiť. V tomto zmysle si môžeme problémy NP predstaviť ako hádanky: môže byť ťažké prísť na odpoveď na hádanku, ale keď sa odpoveď dozvieme, zdá sa, že je zrejmá. V tomto porovnaní (analógii) základná otázka znie: sú hádanky naozaj také ťažké, ako si myslíme, alebo nám niečo uniká?

Keďže tieto typy otázok P verzus NP sú prakticky veľmi dôležité, mnohí matematici, vedci a programátori chcú dokázať všeobecné tvrdenie, že každý rýchlo riešiteľný problém sa dá aj rýchlo vyriešiť. Táto otázka je natoľko dôležitá, že Clayov matematický inštitút dá 1 000 000 dolárov tomu, kto úspešne poskytne dôkaz alebo platné vysvetlenie, ktoré ju vyvráti.

Ak sa do problému zahĺbime, zistíme, že všetky P problémy sú NP problémy: je ľahké skontrolovať, či je riešenie správne, vyriešením problému a porovnaním dvoch riešení. Ľudia však chcú vedieť o opaku: Existujú aj iné NP problémy ako P problémy, alebo sú všetky NP problémy len P problémy? Ak by NP problémy naozaj neboli rovnaké ako P problémy (P ≠ NP), znamenalo by to, že žiadne všeobecné, rýchle spôsoby riešenia týchto NP problémov nemôžu existovať, nech by sme hľadali akokoľvek usilovne. Ak sú však všetky NP problémy P problémy (P = NP), znamenalo by to, že nové, veľmi rýchle metódy riešenia problémov existujú. Len sme ich ešte nenašli.

Keďže ani pri najväčšom úsilí vedcov a matematikov sa zatiaľ nepodarilo nájsť všeobecné, jednoduché metódy na riešenie NP problémov, mnohí ľudia sa domnievajú, že existujú aj iné NP problémy ako P problémy (teda že P ≠ NP je pravda). Väčšina matematikov tiež verí, že je to pravda, ale v súčasnosti to nikto nedokázal prísnou matematickou analýzou. Ak by sa podarilo dokázať, že NP a P sú to isté (P = NP je pravda), malo by to obrovský vplyv na mnohé aspekty každodenného života. Z tohto dôvodu je otázka P verzus NP dôležitou a široko študovanou témou.

Predpokladajme, že niekto chce postaviť dve veže tak, že na seba naskladá kamene s rôznou hmotnosťou. Niekto chce zabezpečiť, aby každá z veží mala presne rovnakú hmotnosť. To znamená, že bude musieť kamene uložiť do dvoch hromád, ktoré majú rovnakú hmotnosť. Ak človek odhadne rozdelenie kameňov, o ktorom si myslí, že bude fungovať, bude pre neho ľahké skontrolovať, či mal pravdu. (Na overenie odpovede môžeme kamene rozdeliť na dve hromady a potom pomocou váh zistiť, či majú rovnakú hmotnosť.) Keďže je ľahké skontrolovať tento problém, ktorý informatici nazývajú "rozdelenie" - jednoduchšie ako ho priamo vyriešiť, ako uvidíme - nie je to problém P. ^[]

Ako ťažko sa to rieši, otvorene? Ak začneme so 100 kameňmi, existuje 2^{100-1}-1 = 633 825 300 114 700 748 351 602 687, teda asi 6,3 x 10^{29} možných spôsobov (kombinácií), ako tieto kamene rozdeliť na dve hromady. Ak by sme mohli každý deň skontrolovať jednu jedinečnú kombináciu hornín, zabralo by to 1,3 x 10^{22} alebo 1 300 000 000 000 000 000 000 000 rokov úsilia. Pre porovnanie, fyzici sa domnievajú, že vesmír má približne 1,4 x 10^{10} rokov (450 000 000 000 000 000 000 alebo približne 4,5 x 10^{17} sekúnd, teda približne jednu bilióntinu času, ktorý by si vyžiadalo naše úsilie pri ukladaní kameňov na hromadu. To znamená, že ak by sme zobrali všetok čas, ktorý uplynul od začiatku vesmíru, museli by sme každú sekundu skontrolovať viac ako dva bilióny (2 000 000 000 000) rôznych spôsobov delenia skál, aby sme skontrolovali všetky rôzne spôsoby.

Ak by sme naprogramovali výkonný počítač na testovanie všetkých týchto spôsobov delenia hornín, mohli by sme byť schopní skontrolovať , 1, 000{\displaystyle000 1 000 000} kombinácií za sekundu pomocou súčasných systémov. To znamená, že na otestovanie všetkých spôsobov delenia hornín by bolo potrebné ešte , 2, 000{\displaystyle000 2 000 000} veľmi výkonných počítačov, ktoré by pracovali od vzniku vesmíru.

Je však možné nájsť spôsob, ako rozdeliť kamene na dve rovnaké hromady bez toho, aby sa museli kontrolovať všetky kombinácie. Otázka "Je P rovné NP?" je skratkou pre otázku, či nejaká takáto metóda môže existovať.

Existuje mnoho dôležitých problémov NP, ktoré ľudia nevedia vyriešiť spôsobom, ktorý by bol rýchlejší ako testovanie všetkých možných odpovedí. Tu je niekoľko príkladov:

• Obchodný cestujúci chce navštíviť 100 miest autom, pričom svoju cestu začne a ukončí doma. Má obmedzené zásoby benzínu, takže môže prejsť celkovo len 10 000 kilometrov. Chce vedieť, či dokáže navštíviť všetky mestá bez toho, aby mu došiel benzín.
• Škola ponúka 100 rôznych tried a učiteľ musí vybrať jednu hodinu pre záverečnú skúšku každej triedy. Aby sa predišlo podvádzaniu, všetci študenti, ktorí navštevujú danú triedu, musia skúšku pre túto triedu vykonať v rovnakom čase. Ak študent navštevuje viac ako jednu triedu, všetky tieto skúšky musia byť v inom čase. Učiteľ chce vedieť, či môže naplánovať všetky skúšky na ten istý deň, aby každý študent mohol absolvovať skúšku z každej svojej triedy.
• Farmár chce na trh zobrať 100 melónov rôznej hmotnosti. Potrebuje ich zabaliť do krabíc. Do každej škatule sa zmestí len 20 kg bez toho, aby sa rozbila. Farmárka potrebuje vedieť, či jej bude stačiť 10 krabíc na to, aby odniesla všetkých 100 melónov na trh. (Toto je triviálne, ak ani jeden melón neváži viac ako 2 kg, potom do každej z debien môže umiestniť ľubovoľných 10, ak ani desať melónov neváži viac ako 2 kg, potom do každej debny môže umiestniť jeden z nich atď. rýchle riešenie; pozorovanie bude kľúčom k akémukoľvek rýchlemu riešeniu, ako je tento problém alebo problém množiny čísel).
• Veľká umelecká galéria má veľa miestností a každá stena je pokrytá množstvom drahých obrazov. Majiteľ galérie chce kúpiť kamery na sledovanie týchto obrazov pre prípad, že by sa zlodej pokúsil niektorý z nich ukradnúť. Chce vedieť, či mu bude stačiť 100 kamier, aby mal istotu, že každý obraz vidí aspoň jedna kamera.
• Problém kliky: Riaditeľ školy má zoznam žiakov, ktorí sa navzájom kamarátia. Chce nájsť skupinu 10 % študentov, ktorí sa všetci navzájom kamarátia.

V uvedenom príklade vidíme, že pri {\displaystyle100 100} horninách existuje {\displaystyle2100 2^{100}} spôsobov rozdelenia množiny hornín. Pri n {\displaystyle n} kameňoch existuje n2 {\displaystyle 2^{n}} kombinácií. Funkcia f ( n ) = n 2{\displaystyle f(n)=2^{n}} je exponenciálna funkcia. Je dôležitá pre NP, pretože modeluje najhorší možný počet výpočtov, ktoré sú potrebné na vyriešenie problému, a tým aj najhorší možný čas potrebný na jeho vyriešenie.

A doteraz si riešenia ťažkých problémov vyžadovali rádovo n 2{\displaystyle 2^{n}} výpočtov. Pre každý konkrétny problém ľudia našli spôsob, ako znížiť počet potrebných výpočtov. Niekto môže prísť na spôsob, ako urobiť len 1 % z najhoršieho možného počtu výpočtov, a to ušetrí veľa výpočtov, ale stále je to ×0.01 ( n2 ) {\displaystyle 0,01\times (2^{n})} výpočtov. A každý ďalší kameň stále zdvojnásobuje počet výpočtov potrebných na vyriešenie problému. Existujú poznatky, ktoré môžu priniesť metódy na vykonanie ešte menšieho počtu výpočtov, ktoré vytvárajú varianty modelu: napr. n2 / n {\displaystyle 2^{n}/n^{3}}3 . Ale exponenciálna funkcia stále dominuje, keď n {\displaystyle n} rastie.

Zoberme si problém plánovania skúšok (opísaný vyššie). Ďalej predpokladajme, že je 15 000 študentov. Existuje počítačový program, ktorý preberá rozvrhy všetkých 15000 študentov. Spustí sa za hodinu a vypíše rozvrh skúšok tak, aby všetci študenti stihli urobiť skúšky za jeden týždeň. Spĺňa množstvo pravidiel (žiadne skúšky za sebou, nie viac ako 2 skúšky v priebehu 28 hodín, ...), aby sa obmedzil stres počas skúškového týždňa. Program beží jednu hodinu v polovici semestrálnej prestávky a každý pozná svoj rozvrh skúšok s dostatkom času na prípravu.

V nasledujúcom roku je však o 10 študentov viac. Ak ten istý program beží na tom istom počítači, potom sa tá jedna hodina zmení na {\displaystyle210 2^{10}} hodín, pretože každý ďalší študent zdvojnásobí výpočty. To je {\displaystyle6 6} týždňov! Ak by bolo ďalších 20 študentov, potom

220  {\displaystyle 2^{20}} hodín = {\displaystyle1048576 1048576} hodín ~ {\displaystyle43691 43691} dní ~ {\displaystyle113 113} rokov

Pre {\displaystyle15000 15000} študentov to teda trvá jednu hodinu. Pre {\displaystyle15020 15020} študentov to trvá {\displaystyle113 113} rokov.

Ako vidíte, exponenciálne funkcie rastú naozaj rýchlo. Väčšina matematikov sa domnieva, že riešenie najťažších NP problémov si vyžaduje exponenciálny čas.

Matematici môžu ukázať, že existujú niektoré NP problémy, ktoré sú NP-úplné. NP-úplný problém je prinajmenšom rovnako ťažko riešiteľný ako akýkoľvek iný NP problém. To znamená, že ak by niekto našiel metódu na rýchle riešenie akéhokoľvek NP-úplného problému, mohol by tú istú metódu použiť na rýchle riešenie každého NP problému. Všetky uvedené problémy sú NP-Complete, takže ak by predavač našiel spôsob, ako rýchlo naplánovať cestu, mohol by to povedať učiteľke a tá by mohla tú istú metódu použiť na naplánovanie skúšok. Farmár by mohol použiť tú istú metódu na určenie toho, koľko debien potrebuje, a žena by mohla použiť tú istú metódu na nájdenie spôsobu, ako postaviť svoje veže.

Pretože metóda, ktorá rýchlo vyrieši jeden z týchto problémov, môže vyriešiť všetky, je veľa ľudí, ktorí ju chcú nájsť. Keďže však existuje veľmi veľa rôznych NP-úplných problémov a nikto doteraz nenašiel spôsob, ako rýchlo vyriešiť čo i len jeden z nich, väčšina odborníkov sa domnieva, že rýchle riešenie NP-úplných problémov nie je možné.

Základné vlastnosti

V teórii výpočtovej zložitosti je trieda zložitosti NP-úplná (skrátene NP-C alebo NPC) trieda problémov, ktoré majú dve vlastnosti:

• Je v množine problémov NP (nedeterministický polynomiálny čas): Každé dané riešenie problému sa dá rýchlo overiť (v polynomiálnom čase).
• Je tiež v množine NP-ťažkých problémov: Tie, ktoré sú aspoň tak ťažké ako najťažšie problémy v NP. Problémy, ktoré sú NP-ťažké, nemusia byť prvkami NP, ba dokonca nemusia byť ani rozhodnuteľné.

Formálny prehľad

NP-úplná je podmnožina NP, množina všetkých rozhodovacích problémov, ktorých riešenia možno overiť v polynomiálnom čase; NP možno ekvivalentne definovať ako množinu rozhodovacích problémov riešiteľných v polynomiálnom čase na stroji. Problém p v NP je tiež v NPC vtedy a len vtedy, ak sa každý iný problém v NP transformuje na p v polynomiálnom čase. NP-úplný sa mal používať ako prídavné meno: problémy v triede NP-úplný boli ako problémy NP+úplný.

NP-úplné problémy sa študujú, pretože sa zdá, že schopnosť rýchlo overiť riešenie problému (NP) koreluje so schopnosťou rýchlo vyriešiť problém (P). Zistilo sa, že každý problém v NP je rýchlo riešiteľný - ako sa nazýva množina problémov P = NP:. Jediný problém v NP-komplete sa rieši rýchlo, rýchlejšie ako každý problém v NP tiež rýchlo riešený, pretože definícia problému v NP-komplete hovorí, že každý problém v NP musí byť rýchlo redukovateľný na každý problém v NP-komplete (je redukovateľný v polynomiálnom čase). [1]

Príklady

Je známe, že problém splniteľnosti boolovských úloh je NP úplný. V roku 1972 Richard Karp sformuloval 21 problémov, ktoré sú známe ako NP-úplné. Tieto problémy sú známe ako Karpových 21 NP-úplných problémov. Patria medzi ne problémy, ako napríklad problém celočíselného programovania, ktorý aplikuje techniky lineárneho programovania na celé čísla, problém knapsack alebo problém vrcholového pokrytia.