primul lucru de înțeles este că P și NP clasifică limbile, nu problemele. Pentru a înțelege ce înseamnă acest lucru, avem nevoie mai întâi de alte definiții.
un alfabet este un set finit de simboluri care nu este gol.
{01} este un alfabet ca și setul de caractere ASCII. {} nu este un alfabet pentru că este gol. N (numerele întregi) nu este un alfabet deoarece nu este finit.
să fie un alfabet. O concatenare ordonată a unui număr finit de simboluri de la SEC.
șirul101 este un cuvânt Peste alfabet {01}. Cuvântul gol (de multe ori scris ca un cuvânt) este un cuvânt Peste orice alfabet. Șirul penguin este un cuvânt deasupra alfabetului care conține caracterele ASCII. Notația zecimală a numărului de numere nu este un cuvânt Peste alfabet {.0123456789} pentru că nu este finit.
lungimea unui cuvânt w, scris ca| w/, este numărul de simboluri din el.
de exemplu,/hello | = 5 și| Irak / = 0. Pentru orice cuvânt w,| w / n și, prin urmare, finit.
să fie un alfabet. Setul conține toate cuvintele de mai sus, inclusiv cele de mai sus. Setul de articole din setul de articole din setul de articole din setul de articole din setul de articole din setul de articole din setul de articole. Pentru n ∈ N, Σn este un set de cuvinte de lungime n.
Pentru fiecare alfabet Σ, Σ 锛 și Σ+ sunt infinit numărabile seturi. Pentru setul de caractere ASCII, expresiile regulate .* și .+ desemnează, respectiv, și, respectiv, și, respectiv, și, respectiv, și, respectiv, și, respectiv, și, respectiv, și, respectiv,.
{01}7 este setul de coduri ASCII pe 7 biți {00000000000001111111101}32 este setul de valori întregi pe 32 de biți.
să fie un alfabet, iar L⊆ XV. L se numește o limbă de peste XV.
pentru un alfabet, setul gol și numărul de limbi sunt triviale față de numărul de limbi. Primul este adesea denumit limba goală. Limba goală {} și limba care conține numai cuvântul gol {XV} sunt diferite.
subsetul {01}32 care corespunde valorilor non-NaN IEEE 754 în virgulă mobilă este un limbaj finit.
limbile pot avea un număr infinit de cuvinte, dar fiecare limbă este numărabilă. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. Setul infinit de șiruri {23571113, …} denotarea numerelor prime în notație zecimală este un subset propriu al acestora. Limbajul care conține toate cuvintele care se potrivesc cu expresia regulată?\d+\.\d*(?\d+)? este un limbaj peste setul de caractere ASCII (care denotă un subset al expresiilor valide în virgulă mobilă definite de limbajul de programare C).
nu există o limbă care să conțină toate numerele reale (în orice notație), deoarece setul de numere reale nu este numărabil.
să fie un alfabet, iar L⊆ XV. O mașină d decide l dacă pentru fiecare intrare w ∈ int calculează funcția caracteristică XL(W) în timp finit. Funcția caracteristică este definită ca
χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.o astfel de mașină este numită decider pentru L. scriem „D(w) = x” pentru „dat w, D ieșiri x”.
există multe modele de mașini. Cel mai general care este în uz practic astăzi este modelul unei mașini Turing. O mașină Turing are stocare liniară nelimitată grupată în celule. Fiecare celulă poate deține exact un simbol al unui alfabet în orice moment. Mașina Turing își efectuează calculul ca o secvență de pași de calcul. În fiecare pas, poate citi o celulă, eventual suprascrie valoarea sa și poate muta capul de citire/scriere cu o poziție în celula stângă sau dreaptă. Ce acțiune va efectua mașina este controlată de un automat în stare finită.
o mașină cu acces aleatoriu cu un set finit de instrucțiuni și stocare nelimitată este un alt model de mașină care este la fel de puternic ca modelul mașinii Turing.
de dragul acestei discuții, nu ne vom deranja cu modelul precis al mașinii pe care îl folosim, ci mai degrabă este suficient să spunem că mașina are o unitate de control deterministă finită, stocare nelimitată și efectuează un calcul ca o secvență de pași care pot fi numărați.
Din moment ce l-ați folosit în întrebarea dvs., presupun că sunteți deja familiarizați cu notația „big-O”, deci aici este doar o actualizare rapidă.
fie o funcție f: n. Setul O(f) conține toate funcțiile g: n Xctxn pentru care există constante n0 xctxn și C xctxn astfel încât pentru fiecare n xctxn cu n > n0 este adevărat că g(n) xctxcf (n).
acum suntem pregătiți să abordăm adevărata întrebare.
clasa P conține toate limbile L pentru care există o mașină Turing D care decide L și o constantă k inktu N astfel încât pentru fiecare intrare w, D se oprește după cel mult T (|w/) pași pentru o funcție t Inktu O(n inktu nk).
Din moment ce O(n NK), în timp ce matematic corect, este incomod să scrie și să citească, cei mai mulți oameni – să fiu sincer, toată lumea, cu excepția mine – de obicei, scrie pur și simplu o(nk).
rețineți că legătura depinde de lungimea lui w. prin urmare, argumentul pe care îl faceți pentru limba primilor este corect doar pentru numerele din codificările unaray, unde pentru codificarea w a unui număr n, lungimea codificării |w| este proporțională cu n. nimeni nu ar folosi vreodată o astfel de codificare în practică. Folosind un algoritm mai avansat decât încercarea pur și simplu a tuturor factorilor posibili, se poate arăta, totuși, că limbajul numerelor prime rămâne în P dacă intrările sunt codificate în binar (sau la orice altă bază). (În ciuda interesului masiv, acest lucru ar putea fi dovedit doar de Manindra Agrawal, Neeraj Kayal și Nitin Saxena într-o lucrare premiată în 2004, astfel încât să puteți ghici că algoritmul nu este foarte simplu.)
limbile triviale {} și Inksqut și non-triviale {inksqut} sunt în mod evident în P (pentru orice alfabet inksqut). Puteți scrie funcții în limbajul dvs. de programare preferat care iau un șir ca intrare și returnează un boolean care spune dacă șirul este un cuvânt din limba pentru fiecare dintre acestea și dovedește că funcția dvs. are o complexitate polinomială a timpului de rulare?
fiecare limbă regulată (o limbă descrisă printr-o expresie regulată) este în P.
să fie un alfabet, iar L⊆ XV. O mașină V care ia un tuplu codificat de două cuvinte W, C și iese 0 sau 1 după un număr finit de pași este un verificator Pentru l dacă are următoarele proprietăți.
- dat (w, c), V ieșiri 1 numai în cazul în care W, L.
- pentru fiecare W, L, există un C, astfel încât V(W, C) = 1.
c în definiția de mai sus se numește martor (sau certificat).
unui verificator i se permite să dea falsuri negative pentru martorul greșit, chiar dacă w este de fapt în L. cu toate acestea, nu i se permite să dea falsuri pozitive. De asemenea, este necesar ca pentru fiecare cuvânt din limbă să existe cel puțin un martor.
pentru limbajul compus, care conține codificările zecimale ale tuturor numerelor întregi care nu sunt prime, un martor ar putea fi o factorizare. De exemplu,(659, 709) este un martor pentru467231 compozit. Puteți verifica cu ușurință că pe o foaie de hârtie în timp ce fără martorul dat, dovedind că 467231 nu este prim ar fi dificil fără a utiliza un computer.
nu am spus nimic despre cum poate fi găsit un martor potrivit. Aceasta este partea nedeterministă.
clasa NP conține toate limbile L pentru care există o mașină Turing V care verifică L și o constantă k inqc astfel încât pentru fiecare intrare (w, C), V se oprește după cel mult T (|w/) pași pentru o funcție t Inqc(n inqc).
rețineți că definiția de mai sus implică faptul că pentru fiecare w inkt L există un martor c cu| c|inkt T (|w/). (Mașina Turing nu poate privi mai multe simboluri ale martorului.)
NP este un superset de P (de ce?). Nu se știe dacă există limbi care sunt în NP, dar nu în P.
factorizarea întregului nu este o limbă în sine. Cu toate acestea, putem construi un limbaj care reprezintă problema de decizie asociată cu acesta. Adică, o limbă care conține toate tuplurile (n, m) astfel încât n are un factor d cu d ≤ M. să numim acest factor de limbă. Dacă aveți un algoritm pentru a decide factorul, acesta poate fi utilizat pentru a calcula o factorizare completă cu doar cheltuieli generale polinomiale prin efectuarea unei căutări binare recursive pentru fiecare factor prim.
este ușor de arătat că factorul este în NP. Un martor adecvat ar fi pur și simplu factorul D în sine și tot ceea ce verificatorul ar trebui să facă este să verifice dacă d ≤ m și n mod d = 0. Toate acestea se pot face în timp polinomial. (Amintiți-vă, din nou, că lungimea codificării contează și că este logaritmică în n.)
dacă puteți arăta că factorul este și în P, puteți fi sigur că veți obține multe premii interesante. (Și ați rupt o parte semnificativă a criptografiei de astăzi.)
pentru fiecare limbă din NP, există un algoritm de forță brută care îl decide determinist. Pur și simplu efectuează o căutare exhaustivă asupra tuturor martorilor. (Rețineți că lungimea maximă a unui martor este delimitată de un polinom.) Deci, algoritmul dvs. de a decide prime a fost de fapt un algoritm de forță brută pentru a decide compozit.
pentru a răspunde la întrebarea dvs. finală, trebuie să introducem reducerea. Reducerile sunt un concept foarte puternic al informaticii teoretice. Reducerea unei probleme la alta înseamnă practic rezolvarea unei probleme prin rezolvarea unei alte probleme.
să fie un alfabet, iar a și b să fie limbi mai mari decât cel al lui XV. A este polinomial-timp multi-unu reductibil la B dacă există o funcție F: XV cu următoarele proprietăți.
- v.a. v. f. (v.) v. b. pentru toate v. v.
- funcția f poate fi calculată de o mașină Turing pentru fiecare intrare w într-un număr de pași delimitate de un polinom în|w/.
în acest caz, scriem un P B.
de exemplu, lăsați A să fie limba care conține toate graficele (codificate ca matrice de adiacență) care conțin un triunghi. (Un triunghi este un ciclu de lungime 3.) Să fie în continuare B limba care conține toate matricile cu urme diferite de zero. (Urma unei matrice este suma principalelor sale elemente diagonale.) Atunci A este timp polinomial multe-unul reductibil la B. pentru a dovedi acest lucru, trebuie să găsim o funcție de transformare adecvată f. în acest caz, putem seta f pentru a calcula a 3-a putere a matricei de adiacență. Aceasta necesită două produse matrice-matrice, fiecare având complexitate polinomială.
este trivial adevărat că L L. (puteți dovedi în mod oficial?)
vom aplica acest lucru la NP acum.
o limbă L este NP-hard dacă și numai dacă l’ inktv p l pentru fiecare limbă l’ INKTV NP.
o limbă NP-hard poate fi sau nu în NP în sine.
o limbă L este NP-completă dacă și numai dacă
- l NP și
- L este NP-tare.
cel mai faimos limbaj NP-complet este SAT. Conține toate formulele booleene care pot fi satisfăcute. De exemplu, (a ∨ b) ∧ (a ∨ b) ∈ SAT. Un martor valid este {a = 1, b = 0}. Formula (a ∨ b) ∧ (a ∨ b) ∧ b ∉ SAT. (Cum ai dovedi asta?)
nu este dificil să se arate că sat inox NP. Pentru a arăta duritatea NP A SAT este o lucrare, dar a fost făcută în 1971 de Stephen Cook.
odată ce o limbă NP-completă a fost cunoscută, a fost relativ simplu să se arate NP-completitudinea altor limbi prin reducere. Dacă limba A este cunoscută a fi NP-hard, atunci arătând că un p b de la sută arată că și B este NP-hard (prin tranzitivitatea „p de la sută”). În 1972, Richard Karp a publicat o listă cu 21 de limbi pe care le-ar putea arăta NP-complete prin reducerea (tranzitivă) a SAT. (Aceasta este singura lucrare din acest răspuns pe care vă recomand să o citiți. Spre deosebire de celelalte, nu este greu de înțeles și oferă o idee foarte bună despre modul în care funcționează dovedirea NP-completitudinii prin reducere.)
în cele din urmă, un scurt rezumat. Vom folosi simbolurile NPH și NPC pentru a desemna clasele de limbi NP-hard și, respectiv, NP-complete.
- P ⊆ NP
- NPC ⊂ NP și NPC-uri ⊂ NPH, de fapt NPC = NP ∩ NPH prin definiție
- (A ∈ NP) ∧ (B ∈ NPH) ⇒ UN ≤p B
Rețineți că includerea NPC-uri ⊂ NP este adecvată chiar și în cazul în care P = NP. Pentru a vedea acest lucru, spuneți-vă clar că niciun limbaj non-trivial nu poate fi redus la unul banal și există limbi banale în P, precum și limbi non-triviale în NP. Acesta este un caz de colț (nu foarte interesant).
sursa ta principală de confuzie pare să fie că te gândeai la „N” în „o(n) f(n))” ca interpretare a intrării unui algoritm atunci când se referă de fapt la lungimea intrării. Aceasta este o distincție importantă, deoarece înseamnă că complexitatea asimptotică a unui algoritm depinde de codificarea utilizată pentru intrare.
în această săptămână, a fost atins un nou record pentru cel mai mare cunoscut Mersenne prime. Cel mai mare număr prim cunoscut în prezent este 274 207 281 − 1. Acest număr este atât de mare încât îmi dă dureri de cap, așa că voi folosi unul mai mic în exemplul următor: 231 – 1 = 2 147 483 647. Poate fi codificat în moduri diferite.
- prin exponentul său Mersenne ca număr zecimal:
31(2 octeți) - ca număr zecimal:
2147483647(10 octeți) - ca număr unar:
11111…11unde…trebuie înlocuit cu 2 147 483 640 mai1s (aproape 2 gib)
toate aceste șiruri codifică același număr și având în vedere oricare dintre acestea, putem construi cu ușurință orice altă codificare a aceluiași număr. (Puteți înlocui codificarea zecimală cu binar, octal sau hexazecimal dacă doriți. Modifică lungimea doar cu un factor constant.)
algoritmul naiv pentru testarea primalității este doar polinomial pentru codificări unare. Testul de primalitate AKS este polinomial pentru zecimal(sau orice altă bază b 2). Testul de Primalitate Lucas-lehmer este cel mai cunoscut algoritm pentru numerele prime Mersenne Mp cu p un prim impar, dar este încă exponențial în lungimea codificării binare a exponentului Mersenne p (polinom în p).
dacă vrem să vorbim despre complexitatea unui algoritm, este foarte important să fim foarte clari ce reprezentare folosim. În general, se poate presupune că se folosește cea mai eficientă codificare. Adică binar pentru numere întregi. (Rețineți că nu fiecare număr prim este un prim Mersenne, astfel încât utilizarea exponentului Mersenne nu este o schemă generală de codificare.)
în criptografia teoretică, mulți algoritmi sunt transmise în mod oficial un șir complet inutil de k 1s ca primul parametru. Algoritmul nu se uită niciodată la acest parametru, dar îi permite să fie formal polinom în k, care este parametrul de securitate utilizat pentru a regla securitatea procedurii.
pentru unele probleme pentru care limbajul de decizie în codificarea binară este NP-complet, limbajul de decizie nu mai este NP-complet dacă codificarea numerelor încorporate este comutată la unar. Limbile de decizie pentru alte probleme rămân NP-complete chiar și atunci. Acestea din urmă sunt numite puternic NP-complete. Cel mai cunoscut exemplu este ambalarea coșurilor.
este de asemenea (și poate mai interesant) să vedem cum se schimbă complexitatea unui algoritm dacă intrarea este comprimată. Pentru exemplul numerelor prime Mersenne, am văzut trei codificări, fiecare dintre acestea fiind logaritmic mai comprimat decât predecesorul său.
în 1983, Hana Galperin și Avi Wigderson au scris o lucrare interesantă despre complexitatea algoritmilor grafici comuni atunci când codificarea de intrare a graficului este comprimată logaritmic. Pentru aceste intrări, limbajul graficelor care conțin un triunghi de sus (unde era clar în P) devine brusc NP-complet.
și asta pentru că clasele de limbi precum P și NP sunt definite pentru limbi, nu pentru probleme.