am scris despre algoritmi eficienți pentru a rezolva probleme complexe, cum ar fi calea cea mai scurtă, graficul Euler, arborele minim de acoperire etc. Acestea au fost toate poveștile de succes ale designerilor de algoritmi. În acest post, sunt discutate povești de eșec ale informaticii.
toate problemele de calcul pot fi rezolvate de un computer? Există probleme de calcul care nu pot fi rezolvate prin algoritmi chiar și cu timp nelimitat. De exemplu, problema opririi Turing (având în vedere un program și o intrare, dacă programul se va opri în cele din urmă atunci când rulează cu acea intrare sau va rula pentru totdeauna). Alan Turing a dovedit că algoritmul general de rezolvare a problemei de oprire pentru toate perechile posibile de programe-intrări nu poate exista. O parte cheie a dovezii este că mașina Turing a fost utilizată ca definiție matematică a unui computer și a unui program (problema opririi sursei).
starea problemelor NP Complete este o altă poveste de eșec, problemele NP complete sunt probleme al căror statut este necunoscut. Niciun algoritm în timp polinomial nu a fost încă descoperit pentru nicio problemă NP complete și nici nimeni nu a reușit încă să demonstreze că nu există un algoritm în timp polinomial pentru niciunul dintre ei. Partea interesantă este că, dacă oricare dintre problemele NP complete poate fi rezolvată în timp polinomial, atunci toate pot fi rezolvate.
care sunt problemele NP, P, NP-complete și NP-Hard?
P este un set de probleme care pot fi rezolvate de o mașină Turing deterministă în timp polinomial.
NP este un set de probleme de decizie care pot fi rezolvate de o mașină Turing nedeterministă în timp polinomial. P este subset de NP (orice problemă care poate fi rezolvată de mașină deterministă în timp polinomial poate fi rezolvată și de mașină nedeterministă în timp polinomial).informal, NP este un set de probleme de decizie care pot fi rezolvate printr-un timp polinomial printr-un „algoritm Norocos”, un algoritm magic care face întotdeauna o presupunere corectă între setul dat de alegeri (Sursa Ref 1).
problemele NP-complete sunt cele mai grele probleme din setul NP. O problemă de decizie L este NP-completă dacă:1 )L este în NP (orice soluție dată pentru problemele NP-complete poate fi verificată rapid, dar nu există o soluție eficientă cunoscută).2 )fiecare problemă din NP este reductibilă la L în timp polinomial (reducerea este definită mai jos).
o problemă este NP-Hard dacă urmează proprietatea 2 menționată mai sus, nu trebuie să urmeze proprietatea 1. Prin urmare, NP-set complet este, de asemenea, un subset de NP-Hard set.
probleme de decizie vs optimizare
NP-completitudinea se aplică domeniului problemelor de decizie. A fost creat în acest fel, deoarece este mai ușor să comparăm dificultatea problemelor de decizie decât cea a problemelor de optimizare. În realitate, însă, a fi capabil să rezolvăm o problemă de decizie în timp polinomial ne va permite adesea să rezolvăm problema de optimizare corespunzătoare în timp polinomial (folosind un număr polinomial de apeluri la problema deciziei). Deci, discutarea dificultății problemelor de decizie este adesea echivalentă cu discutarea dificultății problemelor de optimizare. (Sursa Ref 2).
De exemplu, luați în considerare problema acoperirii vârfului (dat fiind un grafic, aflați setul de noduri de dimensiuni minime care acoperă toate marginile). Este o problemă de optimizare. Problema deciziei corespunzătoare este, având în vedere graficul nedirecționat G și k, există o acoperire a vârfului cu dimensiunea k?
Ce este reducerea?
fie ca L1 și L2 să fie două probleme de decizie. Să presupunem că algoritmul A2 rezolvă L2. Adică, dacă y este o intrare pentru L2, atunci algoritmul A2 va răspunde Da sau nu, în funcție de faptul dacă y aparține sau nu lui L2.
ideea este de a găsi o transformare de la L1 la L2, astfel încât algoritmul A2 să poată face parte dintr-un algoritm A1 pentru a rezolva L1.
reducerea învățării în general este foarte importantă. De exemplu, dacă avem funcții de bibliotecă pentru a rezolva anumite probleme și dacă putem reduce o nouă problemă la una dintre problemele rezolvate, economisim mult timp. Luați în considerare exemplul unei probleme în care trebuie să găsim calea minimă a produsului într-un grafic direcționat dat, unde produsul căii este înmulțirea greutăților marginilor de-a lungul căii. Dacă avem cod pentru algoritmul lui Dijkstra pentru a găsi calea cea mai scurtă, putem lua Jurnalul tuturor greutăților și putem folosi algoritmul lui Dijkstra pentru a găsi calea minimă a produsului, mai degrabă decât să scriem un cod nou pentru această nouă problemă.
cum se dovedește că o problemă dată este NP completă?
din definiția NP-completă, pare imposibil să se demonstreze că o problemă L este NP-completă. Prin definiție, ne cere să arătăm că fiecare problemă din NP este timpul polinomial reductibil la L. Din fericire, există o modalitate alternativă de a dovedi acest lucru. Ideea este de a lua o problemă cunoscută NP-completă și de ao reduce la L. Dacă reducerea timpului polinomial este posibilă, putem dovedi că L este NP-complet prin tranzitivitatea reducerii (dacă o problemă NP-completă este reductibilă la L în timp polinomial, atunci toate problemele sunt reductibile la L în timp polinomial).
care a fost prima problemă dovedită ca NP-completă?
trebuie să existe o primă problemă NP-completă dovedită prin definiția problemelor NP-Complete. SAT (problema satisfacției booleene) este prima problemă NP-completă dovedită de Cook (vezi cartea CLRS pentru dovadă).
este întotdeauna util să știți despre NP-completitudine chiar și pentru ingineri. Să presupunem că vi se cere să scrieți un algoritm eficient pentru a rezolva o problemă extrem de importantă pentru compania dvs. După o mulțime de gândire, puteți veni doar o abordare exponențială a timpului, care este impracticabilă. Dacă nu știți despre NP-completitudine, puteți spune doar că nu am putut veni cu un algoritm eficient. Dacă știți despre NP-completitudine și dovediți că problema ca NP-completă, puteți spune cu mândrie că soluția de timp polinomial este puțin probabil să existe. Dacă există o soluție în timp polinomial posibilă, atunci această soluție rezolvă o mare problemă a informaticii pe care mulți oameni de știință o încearcă de ani de zile.
vom discuta în curând mai multe probleme NP-Complete și dovada lor pentru NP-completitudine.