Vartiklis: Ant sveiko proto svarstyklių. N-NP problema

Indų kilmės Vinay Deolalikar‘as, dirbantis „Hewlett-Packard“ laboratorijose Kalifornijoje (JAV), teigia, kad išsprendė P ir NP klasių tapatumo problemą, kuri yra viena 7-ių „Tūkstantmečio problemų“, už kurių išsprendimą Clay matematikos institutas skyrė po milijoną dolerių. Iš jų kol kas išspręsta tik viena – Puankarė teiginys iš topologijos srities, kurį įrodė Grigorijus Perelmanas (beje, atsisakęs premijos).

P ir NP klasių tapatumo klausimas yra vienas svarbiausių kompiuterijos moksle. Vinay Deolalikar‘as savo įrodymą pateikė išsamiu rankraščiu, kurį galima perskaityti čia. Anot jo įrodinėjimo, P ir NP klasės nėra lygios. Jei įrodymas teisingas, tai reikštų, kad uždavinio sprendinio teisingumo nustatymas nėra tas pat kaip to sprendinio suradimas.

Visada yra vienas būdas, kaip kompiuteris gali išspręsti uždavinį – tiesiog išbandydamas visas įmanomas kombinacijas. Tačiau, pavyzdžiui, jei bandote „nulaužti“ užšifruotą informaciją, tai gali trukti nepaprastai ilgai. P ir NP problemos klausimo esmė – ar galima automatizuoti kūrybiškumą? Vinay Deolalikar‘as įrodymas teigtų, kad negalima.

Kaip pagrindinį pavyzdį ir idėją, Deolalikar‘o įrodyme panaudojamas bulinio užtikrintumo uždavinys (k-SAT). Šio tipo uždaviniai nagrinėja loginę išraišką, susidedančią tik iš „ir“, „arba“ bei „ne“ operatorių, kintamųjų ir skliaustų, bandant nustatyti, ar gali kintamieji įgauti tokias „taip“ ir „ne“ reikšmes, kad išraiškos reikšmė būtų „taip“.

Įrodymas bando k-SAT uždavinį perteikti kaip užklausas grafinėse struktūrose. Panaudojama geometrinė FO (LPF) logikos interpretacija, „užgriebianti visas per polinominį laiką paskaičiuojamas užklausas“. Jei k reikšmė yra pakankamai didelė, tada sprendinio erdvė tampa milžiniška ir eksponentinis sprendinių skaičius bus generuojamas per LFP konstrukciją. Tai aiškiai parodo, kad „LPF negali išreikšti užtikrintumo užklausos ... ir atskiria P nuo NP“.

1971-aisiais Stephen Cook, jaunas Toronto un-to profesorius dar “neapsiplunksnavusio” kompiuterių mokslo srityje iškėlė šį klausimą. Nuo tada buvo pateikta vos saujelė galimų sprendimų, kurių visi greitai buvo paneigti. Tad S. Cook labai džiaugiasi Vinay Deolalikar‘o bandymu. Tačiau gilinantis į jo įrodinėjimą, galvą ėmė kaišioti trūkumai. Vinay Deolalikar‘as pateikė pataisytą įrodymo versiją, tačiau išliko nepataisomos konceptualaus lygio problemos.

Matematikai įtaria, kad Vinay Deolalikar‘o įrodymas gali nepraeiti labai paprasto „sveiko proto“ testo, kurio esmė – užtikrinti, kad jis matematinis įrodymas įrodo tik tuos dalykus, apie kuriuos žinome, kad jie teisingi. Jis neturėtų kartu įrodinėti dalykų, apie kuriuos žinome, kad jie neteisingi. Jei Vinay Deolalikar‘as negalės parodyti, kad jo įrodymas tenkina „sveiko proto“ testą, tai tebus „riebi antis“.

P ir NP lygybės klausimas algoritmų teorijoje jau 30 m. yra viena pagrindinių neišspręstų problemų. Teigiamo atsakymo atveju tai reikštų, kad teoriškai įmanoma gerokai greičiau išspręsti daugelį sudėtingų uždavinių. Dabar sudėtingiausius NP uždavinius įmanoma išspręsti tik per eksponentinį laiką, kas nelabai priimtina. P ir NP klasių santykį nagrinėja skaičiavimo sudėtingumo teorija, kuri nagrinėja resursus, būtinus P-NP relations

uždavinio sprendimui. Bendriausi resursai – tai laikas (reikalingų atlikti veiksmų kiekis) bei atmintis.

Palyginkime n² (polinominio, P) ir 2ⁿ (eksponentinio, NP) sudėtingumo algoritmus. Padidinus duomenų kiekį dvigubai, P algoritmo trukmė padidėja 4 k. Tuo tarpu NP algoritmo trukmė padidėja 4 k. pridėjus tik 2 duomenų elementus.

Kitaip tariant, jei per trumpą (polinominį) laiką galima patikrinti kokį nors konkretų atsakymą, tai ar reiškia, kad greitai (per polinominį laiką ir naudojant polinominę atmintį) galima rasti sprendimą?

Pavyzdžiui, ar tiesa, kad tarp skaičių {-2, -3, 15, 14, 7, -10,...} yra tokių, kurių suma lygi 0 (uždavinys apie poaibių sumas)? Atsakymas teigiamas, nes nesunku surasti, kad -2-3+15-10=0 (informacija, būtina teigiamo atsakymo patikrinimui, vadinama sertifikatu). Ar iš čia seka, kad taip pat lengvai bus parinkti šitie skaičiai? Ar patikrinti sertifikatą ir jį rasti yra tas pats sunkumas? Atrodytų, kad parinkti skaičius yra sunkiau.

Pirmąkart klausimą apie P ir NP klasių lygybę 1971 m. iškėlė S. Kukas ir Levinas, Šiuo metu dauguma matematikų mano, kad tos klasės nėra lygios. Vinay Deolalikar‘as teigia tai įrodęs.

Paimkime dviejų matricų sandaugą C=AB
kuri skaičiuojama taip: c_ij = SUM(a_ik b_kj), k kintant nuo 1 iki n, kiekvienam i ir j tarp 1 ir n.

Taip viso atliekama n³ daugybos ir n²(n-1) sudėties operacijų, o bendrai - 2 n³-n² aritmetinių veiksmų.

O ar galima dvi matricas sudauginti greičiau? O taip! Panaudojus Štraseno algoritmą, atliekama O(n^{log 7}) veiksmų.

Uždaviniai, kurių sprendimui žinome polinominio sudėtingumo [ O(n^p ] algoritmus, yra „išsprendžiami“ net tada, kai n >> 1 (aišku, kai p nėra labai didelis skaičius):

Imkim n skirtingų objektų (a₁, a₂, ... a_n).
Reikia sugeneruoti visus skirtingus jų dėstinius (kėlinius): P_n = {( a‘₁, a‘₂, ... a‘_n)}

Skirtingų kėlinių yra n!, todėl net efektyviausių algoritmų sudėtingumas O(n!).
Pagal Stirlingo formulę įvertiname: n! = sqrt(2 pi n) (n/e)ⁿ

Tada kėlinių P_n generavimo laikai (apytiksliai):
T(11) = 0.28 (s); T(12) = 3.4 (s); ...
T(17) = 29.5 (d); T(18) = 532 (d); ...
O T(20) – jau 553 metai (!)

O jei panaudosime lygiagrečiuosius algoritmus? Su 2056 procesoriais T(20) būtų apie 3 mėn., tačiau P₂₁ sugaištume ilgiau nei 5 m.

Padidinus duomenų skaičių dvigubai, polinominio sudėtingumo algoritmų veikimo trukmė padidėja keturgubai.
Eksponentinio sudėtingumo algoritmų veikimo trukmė padidėja du kartus pridėjus vos vieną vienintelį duomenį.

NP (angl. nondeterministic polynomial time) uždavinių klasė tokia, kuriai nežinome polinominio sudėtingumo sprendimo algoritmų, tačiau atlikę O(n^k) veiksmų, galime patikrinti, ar duotasis objektas yra uždavinio sprendinys.

Lankytojų komentarai / pastabos

Mums pastabas, kurias pateikiame žemiau, 2012 m. gegužės 1 d. atsiuntė Žilvinas. Tai mus paskatino įvesti šiame straipsnelyje atsiliepimų skyrelį, kuriame jūs galite diskutuoti, pateikti savo pastabas, papildyti šią temą...

Žilvino žinutė:
Skyrelyje: P ir NP klasių tapatumas
Klaida fragmente:
Palyginkime n^2 (polinominio, P) ir 2^n (eksponentinio, NP) sudėtingumo algoritmus. Padidinus duomenų kiekį dvigubai, P algoritmo trukmė padidėja 4 k. Tuo tarpu NP algoritmo trukmė padidėja 4 k. pridėjus tik 2 duomenų elementus.

Taisymas: Pirmiausia iš pradžių kalbama apie dvigubą pradinių duomenų padidinimą (2*n), vėliau apie padidinimą dviem elementais (n+2), jeigu pradiniai duomenys yra didinami dvigubai, tai P algoritmo trukmė padidėja 4 kartus, o NP algoritmo 2^n kartų (ne 4 k). Jeigu kalbama apie pradinių duomenų padidinimą dviem elementais, tai P algoritmo veikimo laikas padidėja (n^2 + 4*n + 4)/(n^2) k (kuo didesnis n tuo algoritmo veikimo laikas labiau priklauso nuo n^2 atliekų operacijų, kas sąlyginai yra nedaug). Tuo tarpu NP (2^n) padidinus dviem elementais laikas padidėja (2^(n + 2))/(2^n) k => 4 k (kas reiškia, kad su kiekvienu n padidėjimu laikas padidėja dvigubai). Kaip pavyzdį galima pasirinkti konkrečią situaciją:
tarkime turite NP algoritmą, kuris su n = 1 darbą atlieka per 2s, tačiau jeigu n pasirinksite 1000, algoritmo veikimo laikas padidės 2s*2^1000 >= 10^300 s kas yra apytiksliai 10^292 metų. Jeigu būtų įrodyta, kad P = NP tai reikštų, kad galima nulaužti visas dabartines bankų saugumo sistemas, nes jos remiasi tuo, kad žinant savo slaptažodį ir login patikrinti ar jis teisingas užtrunka tiek kiek trunka įvykdyti P klasės algoritmą (sąlyginai trumpai), tačiau nori atspėti slaptažodį reikia vykdyti NP kalsės algoritmą ir išmėginti visus įmanomus variantus, kas iš pavyzdžio tampa aišku, kad užimtų didžiulius kiekius laiko.

Tikiuosi pavyzdys padėjo suprast P ir NP tapatumo problemą. :)

Papildomai: Tiuringas – liūdno likimo genijus
Ar jau rūksta dūmai? Navier Stokes lygtys

Kviečiame bendrauti!

          Jūsų vardas: 
Jūsų el.pašto adresas:

Jūsų žinutė:

Lankytojų žinutės