P-NP: Ant sveiko proto svarstyklių
Indų kilmės Vinay Deolalikaras, 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 Deolalikaras 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 Deolalikaras įrodymas teigtų, kad negalima.
Kaip pagrindinį pavyzdį ir idėją, Deolalikaro į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 Deolalikaro bandymu. Tačiau gilinantis į jo įrodinėjimą, galvą ėmė kaišioti trūkumai. Vinay Deolalikaras pateikė pataisytą įrodymo versiją, tačiau išliko nepataisomos konceptualaus lygio problemos.
Matematikai įtaria, kad Vinay Deolalikaro į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 Deolalikaras 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
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:
- Ar žemėlapyje galima nuspalvinti šalis raudonai, žaliai ir mėlynai taip, kad jokios gretimos nebūtų tos pačios spalvos?
- Ar pateiktas dėžių kiekis tilps į sunkvežimį?
- Ar žinant atstumus tarp miestų, galima juos visus apvažiuoti apsilankant tik kartą, nuvažiuojant ne daugiau 5000 km?
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 Deolalikaras 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):
- tiesinės algebros uždaviniai;
- tikrinių reikšmių paieška;
- matematinės fizikos užduotys;
- kiti...
Nepolinominio sudėtingumo uždaviniai
Imkim n skirtingų objektų (a1, a2, ... an).
Reikia sugeneruoti visus skirtingus jų dėstinius (kėlinius): Pn = {( a1, a2, ... an)}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)nTada 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!
Lankytojų žinutės