P-NP: Ant sveiko proto svarstyklių

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ė teiginystopologijos srities, kurį įrodė Grigorijus Perelmanas (beje, atsisakęs premijos).

Homer and P-NP 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 klasių tapatumas

Iš 7-ių Tūkstantmečio premijos problemų kol kas išspręsta tik Poincarė teorema. Dabar aprašysime dar vieną iš tų problemų.

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 n2 (polinominio, P) ir 2n (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.

Imame NP (angl. nondeterministic polynomial time) uždavinių klasę. Šiems uždaviniams nežinome polinominio sudėtingumo sprendimo algoritmų, tačiau atlikę O (nk) veiksmų, galime patikrinti, ar duotasis objektas yra uždavinio sprendinys.

P NP , bet ar P = NP ?

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.

P klasės pavyzdžiai:

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.


Algoritmų sudėtingumas

Polinominio sudėtingumo uždaviniai

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

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

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

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

Nepolinominio sudėtingumo uždaviniai

Imkim n skirtingų objektų (a1, a2, ... an).
Reikia sugeneruoti visus skirtingus jų dėstinius (kėlinius): Pn = {( a‘1, a‘2, ... 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)n

Tada kėlinių Pn 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 P21 sugaištume ilgiau nei 5 m.

NP sudėtingumo uždaviniai

Palyginkime n2 ir 2n sudėtingumo algoritmus.

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(nk) veiksmų, galime patikrinti, ar duotasis objektas yra uždavinio sprendinys.

Aišku, kad P < NP, tačiau ar P <> NP?

Ši problema yra ir tūkstantmečio problemų sąraše (iš kurio teįrodytas tik Puankarė teiginys); apie ją daugiau žr. >>>>

Papildomai skaitykite:
Jų begalinė išmintis
Tūkstantmečio problemos
Žmonės prieš kompiuterius
Žaidimų teorijos panaudojimas
Iniciatyva: Matematikos keliu
Amerikai matematika nereikalinga!
Netiesinis mąstymas: išspręsti neišsprendžiamą
Simpsonų trauka ir žaidimas skaičiais
Matematikos ir fizikos šmaikštumai
A. Puankarė. Mokslas ir hipotezė
P. Fejerabendas prieš mokslą
Kur viešpatauja chaosas?
Meilės sinusoidė
Matroidai

 

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