Practic sunteți corect despre P și NP, dar nu despre NP-hard și NP-complete.

Pentru început, iată definițiile super-concise ale celor patru clase de complexitate în cauză:

• P este clasa problemelor de decizie care pot fi rezolvate în timp polinomial de o mașinărie Turing deterministă.

• NP este clasa problemelor de decizie care pot fi rezolvate în timp polinomial de o mașină Turing nedeterministă. În mod echivalent, este clasa problemelor care pot fi verificate în timp polinomial de către o mașinărie Turing deterministă.

• NP-hard este clasa problemelor de decizie la care pot apărea toate problemele din NP redusă la în timp polinomial de o mașinărie Turing deterministă.

• NP-complet este intersecția dintre NP-hard și NP. În mod echivalent, NP-complet este clasa problemelor de decizie din NP, la care toate celelalte probleme din NP pot fi reduse în timp polinomial de către o mașinărie Turing deterministă.

Și aici „diagrama sa Euler din Wikipedia care arată relațiile dintre aceste patru clase (presupunând că P nu este egal cu NP):

Partea despre care presupun că sunteți cel mai necunoscut sau confuz de este noțiunea de „reducere a timpului polinomial” de la problema X la problema Y. O reducere de la X la Y este pur și simplu un algoritm A care rezolvă X utilizând un alt algoritm B care rezolvă problema Y. Această reducere se numește „ reducerea timpului polinomial „dacă toate părțile lui A, altele decât B, au o complexitate de timp polinomială. Ca un exemplu banal, problema găsirii celui mai mic element dintr-o matrice este reductibilă în timp constant la problema de sortare, deoarece puteți sorta matricea și apoi întoarce primul element al matricei sortate.

un lucru ușor de ratat în ceea ce privește definiția NP-hard este că reducerea merge de la problemele NP la problema NP-hard, dar nu neapărat invers . Aceasta înseamnă că problemele NP-hard ar putea fi în NP, sau într-o clasă de complexitate mult mai mare (după cum puteți vedea din diagrama Euler), sau s-ar putea să nu fie chiar probleme decisive.De aceea oamenii spun adesea ceva de genul „NP-hard înseamnă cel puțin la fel de greu ca NP” atunci când încearcă să explice aceste lucruri în mod informal.

Problema opririi este un bun exemplu de problemă NP-hard care „nu este clar în NP, așa cum explică Wikipedia :

Este ușor să dovediți că problema de oprire este NP-hard, dar nu este NP-completă. De exemplu, problema de satisfacție booleană poate fi redusă la problema de oprire prin transformarea ei în descrierea unei mașini Turing care încearcă toate atribuțiile de valoare de adevăr și când găsește una care îndeplinește formula se oprește și altfel intră într-o buclă infinită. Este, de asemenea, ușor de observat că problema de oprire nu se află în NP, deoarece toate problemele din NP sunt decizibile într-un număr finit de operații, în timp ce problema de oprire, în general, este indecidabilă.

Comentarii

• @Nakano Intuitiv, este ‘ sa ” reducere ” în sensul că o problemă devine o subproblemă a altei probleme. Faptul că unele dintre aceste reduceri sporesc complexitatea în loc să o scadă prin alegerea slabă a ” subproblemă ” înseamnă pur și simplu că nu veți folosi niciodată aceste reduceri în orice cod din lumea reală. Deși, sincer, NP-hard mă pare o clasă ciudată și nu teribil de interesantă; poate fi mai fructuos să îl ignori și să te gândești doar la NP-complete ca la setul de probleme NP la care se reduc toate celelalte probleme NP.
• @Nakano stackoverflow.com/questions/12637582/… Cred că răspunsul scurt este că atunci când oamenii vorbesc despre factorizarea numărului întreg ca fiind NP, ei ‘ re vorbim în mod normal despre numere întregi cu adevărat uriașe, pentru care, în general, începeți să vă faceți dovezile mari-O cu n ca ” numărul de biți pe care întregul îl ocupă în memorie „376415b7d2”>

Factorizarea întregului este citată ca exemplu de NP, dar nu înțeleg de ce nu este P, personal, deoarece factorizarea procesului necesită timp O (sqrt (n)).

În scopul claselor de complexitate, n este lungimea intrării. Deci, dacă doriți să luați în calcul factorul întreg k, n nu este k ci log k, numărul de biți (sau orice altceva) necesar pentru a nota numărul. Deci factorizarea numărului întreg este O(sqrt(k)) așa cum spui, dar acesta este O(sqrt(2n)) care este O(2(n/2)).

NP-Hard Presupun că este plin de necunoscute. Greu de verificat, greu de rezolvat.

Nu. NP-Hard se referă doar la cât de greu este de rezolvat o problemă.

Problemele NP-Hard sunt cel puțin dure ca fiind cea mai grea problemă din NP. Știm că sunt cel puțin atât de greu, deoarece dacă am avea un algoritm polinomial-timp pentru o problemă NP-Hard, am putea adapta acel algoritm la orice problemă din NP.

NP-Complete Nu înțeleg deloc

NP- Complet înseamnă că o problemă este atât NP, cât și NP-Hard. Înseamnă că putem verifica rapid o soluție (NP), dar este cel puțin la fel de grea ca cea mai grea problemă din NP (NP-Hard).

Nu știu cu adevărat ce înseamnă să fie nedeterminist.

Non -determinismul este o definiție alternativă a NP. O mașină de turing nedeterministă este în mod eficient capabilă să se dubleze în orice moment și să aibă fiecare duplicat să ia o cale de execuție diferită. Conform acestei definiții, NP este ansamblul problemelor care pot fi rezolvate în timp polinomial de către un computer decât se poate copia în mod liber. Se pare că acesta este exact același set de probleme care pot fi verificate în timp polinomial.

Comentarii

• Deci este posibil pentru $ O ( n ^ k) $ algoritmi de timp să fie probleme NP?
• k este un număr real constant? Da. Toate problemele P sunt, de asemenea, probleme NP. Evident, orice puteți rezolva în timp polinomial poate fi verificat și în timp polinomial.
• Cum este definită de fapt lungimea / dimensiunea aici? De exemplu, aș putea scrie doar $ n $ într-o bază mare și să-i scad lungimea atunci când sunt scrise. Ce se întâmplă cu problemele care ‘ nu se ocupă în mod explicit de numere întregi, dar spunem grafice cu vârfuri $ V $ și margini $ E $ etc.
• @Nakano, de fapt o bază mare nu l-ar modifica ‘, deoarece ar fi doar o diferență de factor constantă. Deci, nu ar ‘ efect polinom vs non-polinom. Totuși, dacă ați scrie numărul în unar, atunci acesta l-ar schimba.
• @Nakano, hmm … Nu aș îndrăzni să încerc să explic complexitatea ‘ cursuri la un copil de cinci ani. : P

Primul lucru de înțeles este că P și NP clasificați limbile , nu problemele . Pentru a înțelege ce înseamnă acest lucru, mai întâi avem nevoie de alte definiții.

Un alfabet este un set finit non-gol de simboluri.

{0 , 1} este un alfabet la fel ca setul de caractere ASCII. {} nu este un alfabet, deoarece este gol. N (numărul întreg) nu este un alfabet deoarece nu este finit.

Să Σ fii un alfabet. O concatenare ordonată a unui număr finit de simboluri din Σ se numește cuvânt peste Σ .

Șirul 101 este un cuvânt peste alfabetul {0, 1}. cuvântul gol (adesea scris ca ε ) este un cuvânt peste orice alfabet. Șirul penguin este un cuvânt peste alfabet care conține caracterele ASCII. Notația zecimală a numărului π nu este un cuvânt peste alfabetul {., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} deoarece nu este finit.

lungimea a unui cuvânt w , scris ca | w |, este numărul de simboluri în ea.

De exemplu, | hello | = 5 și | ε | = 0. Pentru orice cuvânt w , | w | ∈ N și, prin urmare, finit.

Să Σ fii un alfabet. Setul Σ ^＊ conține toate cuvintele peste Σ , inclusiv ε . Setul Σ ⁺ conține toate cuvintele din Σ , cu excepția ε . Pentru n ∈ N , Σ ⁿ este setul de cuvinte de lungime n .

Pentru fiecare alfabet Σ , Σ ^＊ și Σ ⁺ sunt infinite seturi numărabile .Pentru setul de caractere ASCII Σ _ASCII , expresiile regulate .* și .+ denota Σ _ASCII ^＊ și Σ _ASCII ⁺ , respectiv.

{0, 1} ⁷ este setul de coduri ASCII pe 7 biți {0000000, 0000001, …, 1111111}. {0, 1} ³² este setul de valori întregi pe 32 de biți.

Fie Σ un alfabet și L ⊆ Σ ^＊ . L se numește limbaj peste Σ .

Pentru un alfabet Σ , setul gol și Σ ^＊ sunt limbaje banale peste Σ . Primul este adesea denumit limbă goală . Limba goală {} și limba care conține doar cuvântul gol { ε } sunt diferite.

Subsetul din {0, 1} ³² 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ă poate fi numărată. Setul de șiruri {1, 2, …} care indică numerele întregi în notație zecimală este un limbaj infinit peste alfabet {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9}. Setul infinit de șiruri {2, 3, 5, 7, 11, 13, …} indicând numerele prime în notație zecimală este un subset corespunzător al acestuia. Limba care conține toate cuvintele care se potrivesc cu expresia regulată [+-]?\d+\.\d*([eE][+-]?\d+)? este o limbă peste setul de caractere ASCII (denotând un subset al expresiilor valabile în virgulă mobilă definite de limbajul de programare C).

Nu există limbaj care să conțină toate numerele reale (în nicio notare) deoarece setul de numere reale nu poate fi numărat.

Să Σ fie un alfabet și L ⊆ Σ ^＊ . O mașină D decide L dacă pentru fiecare intrare w ∈ Σ ^＊ calculează funcția caracteristică χ _L ( w ) în timp finit. Funcția caracteristică este definită ca

χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.

O astfel de mașină se numește decider pentru L . Scriem „ D ( w ) = x ” pentru „dat w , D ieșiri x ”.

Există multe modele de mașini. Cea mai generală care este în uz practic astăzi este modelul unei Mașină 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 al timpului. Mașina Turing își efectuează calculul ca o succesiune de pași de calcul. În fiecare pas, poate citi o celulă, poate suprascrie valoarea și poate muta capul de citire / scriere cu o poziție în celula stângă sau dreapta. Ce acțiune va efectua mașina este controlată de un automat cu stare finită.

O mașină cu acces aleator 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.

Pentru această discuție, nu ne vom deranja cu modelul de mașină precis 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 succesiune de pași asta poate fi numărat.

Deoarece l-ați folosit în întrebarea dvs., presupun că sunteți deja familiarizat cu notația „big-O” deci aici este doar o reîmprospătare rapidă.

Să f : N → fi o funcție.Setul O ( f ) conține toate funcțiile g : N → N pentru care există constante n ₀ ∈ N și c ∈ N astfel încât pentru fiecare n ∈ N cu n > n ₀ este adevărat că g ( n ) ≤ c f ( 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 ∈ N astfel încât pentru fiecare intrare w , D se oprește după cel mult T (| w |) pași pentru o funcție T ∈ O ( n ↦ n ^k ).

De la O ( n ↦ n ^k ), deși corect matematic, este incomod să scrie și să citească, majoritatea oamenilor – sincer să fiu, toată lumea cu excepția mea – de obicei scrie simplu O(n^k ).

Rețineți că legătura depinde de lungimea w . Prin urmare, argumentul pe care îl faceți pentru limbajul primelor este corect doar pentru numerele din codificări unaray , unde pentru codarea w a un număr n , lungimea codă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 simpla încercare 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 către 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.)

Limbajele banale {} și Σ ^＊ și limbajul non-trivial { ε } sunt evident în P (pentru orice alfabet Σ ). 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 demonstrați că funcția dvs. are complexitate polinomială în timpul rulării?

p> Fiecare limbă regulată (o limbă descrisă printr-o expresie regulată) este în P .

Fie Σ un alfabet și L ⊆ Σ ^＊ . O mașină V care ia un tuplu codificat de două cuvinte w , c ∈ Σ ^＊ și afișează 0 sau 1 după un număr finit de pași este un verificator pentru L dacă are următoarele proprietăți.

• Date ( w , c ), V rezultă 1 numai dacă w ∈ L .
• Pentru fiecare w ∈ L , există există un c ∈ Σ ^＊ astfel încât V ( w , c ) = 1.

c din definiția de mai sus se numește martor (sau certificat ) .

Un verificator are voie să dea negative negative pentru martorul greșit, chiar dacă w este de fapt în L . Cu toate acestea, nu este permis să dea falsuri pozitive. De asemenea, este necesar ca pentru fiecare cuvânt din limbă să existe cel puțin un martor.

Pentru limba COMPOSITE, care conține codificări zecimale ale tuturor numerelor întregi care nu sunt nu prime , un martor ar putea fi o factorizare. De exemplu, (659, 709) este martor pentru 467231 ∈ COMPOSITE. Puteți verifica cu ușurință că pe o foaie de hârtie, fără a fi dat martorul, să demonstrați că 467231 nu este prim ar fi dificil fără a utiliza un computer.

Nu am spus nimic despre modul în care poate fi un martor adecvat 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 ∈ N astfel încât pentru fiecare input ( w , c ), V se oprește după cel mult T (| w |) pași pentru o funcție T ∈ O ( n ↦ n^k ).

Rețineți că definiția de mai sus implică faptul că pentru fiecare w ∈ L există un martor c cu | c | ≤ 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 numărului întreg nu este o limbă în sine. Cu toate acestea, putem construi un limbaj care să reprezinte problema deciziei asociate acestuia. Adică, un limbaj care conține toate tuplurile ( n , m ) astfel încât n are un factor d cu d ≤ m . Să numim această limbă FACTOR. Dacă aveți un algoritm care să decidă FACTOR, acesta poate fi folosit pentru a calcula o factorizare completă cu doar overhead polinomial, efectuând o căutare binară recursivă pentru fiecare factor primar.

Este ușor să arătați că FACTOR este în NP . Un martor adecvat ar fi pur și simplu factorul d în sine și tot ce ar trebui să facă verificatorul 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ă contează lungimea codării și că este logaritmică în n .)

Dacă puteți arăta că FACTOR este, de asemenea, în P , puteți fi sigur că veți obține multe premii interesante. (Și ați rupt o parte semnificativă din criptografia de astăzi.)

Pentru fiecare limbă din NP , există un algoritm de forță brută care decide em 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. pentru a decide PRIMES a fost de fapt un algoritm de forță brută pentru a decide COMPOZITUL.

Pentru a răspunde la întrebarea dvs. finală, trebuie să introducem reducere . Reducerile sunt un concept foarte puternic al informaticii teoretice. Reducerea unei probleme la alta înseamnă practic rezolvarea unei probleme prin rezolvarea alteia problemă.

Fie Σ un alfabet și A și B sunt limbi peste Σ . A este polinomial-time many-one reductibil la B dacă există o funcție f : Σ ^＊ → Σ ^＊ cu următoarele proprietăți.

• w ∈ A   ⇔   f ( w ) ∈ B   pentru toți w ∈ Σ ^＊ .
• Funcția f poate fi calculată de o mașină Turing pentru fiecare intrare w într-un număr de pași delimitați de un polinom în | w |.

În acest caz, scriem A ≤ _p B .

Pentru de exemplu, fie A limbajul care conține toate graficele (codificate ca matrice de adiacență) care conțin un triunghi. (Un triunghi este un ciclu de lungime 3.) Fie în continuare B limbajul care conține toate matricile cu urmă diferită de zero. (Urma unei matrici este suma elementelor sale diagonale principale.) Atunci A este polinomial mult-unu reductibil la B . Pentru a demonstra acest lucru, trebuie să găsim o funcție de transformare adecvată f . În acest caz, putem seta f pentru a calcula puterea 3 ^rd a matricei de adiacență. Acest lucru necesită două produse matrice-matrice, fiecare dintre acestea având complexitate polinomială.

Este trivial adevărat că L ≤ _p L . (Puteți să o demonstrați în mod oficial?)

Vom aplica acum acest lucru la NP .

O limbă L este NP -hard dacă și numai dacă L „≤ _p L pentru fiecare limbă L ” ∈ NP .

Un limbaj dur NP poate fi sau nu în NP în sine.

O limbă L este NP -complete dacă și numai dacă

• L ∈ NP și
• L este NP -hard.

Cea mai faimoasă limbă completă NP 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 ați dovedi asta?)

Nu este dificil să arătați că SAT ∈ NP . Pentru a arăta duritatea NP a SAT este o lucrare, dar a fost realizată în 1971 de Stephen Cook .

Odată ce acel limbaj complet NP a fost cunoscut, a fost relativ simplu să se arate completitudinea NP a altor limbi prin reducere. Dacă se știe că limba A este NP -hard, atunci se arată că A ≤ _p B arată că și B este NP -hard (de asemenea, prin tranzitivitatea „≤ _p ”). În 1972, Richard Karp a publicat o listă cu 21 de limbi pe care le-ar putea arăta ca fiind NP -complete prin reducerea (tranzitivă) a SAT. (Aceasta este singura lucrare din acest răspuns pe care, de fapt, vă recomand să o citiți. Spre deosebire de celelalte, nu este greu de înțeles și oferă o idee foarte bună despre cum funcționează demonstrarea completitudinii NP prin reducere. )

În sfârșit, un scurt rezumat. Vom folosi simbolurile NPH și NPC pentru a indica clasele limbilor complete NP și NP respectiv.

• P ⊆ NP
• NPC ⊂ NP și NPC ⊂ NPH , de fapt NPC = NP ∩ NPH prin definiție
• ( A ∈ NP ) ∧ ( B ∈ NPH )   ⇒   A ≤ _p B

Rețineți că includerea NPC ⊂ NP este adecvată chiar și în cazul în care P = NP . Pentru a vedea acest lucru, clarificați-vă că niciun limbaj non-trivial nu poate fi redus la unul trivial și că există și limbi triviale în P ca limbaje non-banale în NP . Thi s este un caz de colț (nu foarte interesant).

Addendum

Sursa 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ă, o nouă înregistrare pentru cel mai mare Mersenne prime a fost atins. Cel mai mare număr prim cunoscut în prezent este 2 ^{74   207   281} – 1. Acest număr este atât de mare că îmi dă dureri de cap, așa că voi folosi una mai mică în următorul exemplu: 2 ³¹ – 1 = 2   147   483   647. Poate fi codificat în diferite moduri.

• de exponentul său Mersenne ca număr zecimal: 31 (2 octeți)
• ca număr zecimal: 2147483647 (10 octeți)
• ca unar număr: 11111…11 unde … trebuie înlocuit cu 2   147   483   încă 640 1 s (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 cu același număr. (Puteți înlocui codificarea zecimală cu binar, octal sau hexadeci mal dacă vrei. Acesta modifică doar lungimea cu un factor constant.)

Algoritmul naiv pentru testarea primalității este doar polinomial pentru codificări unare. Testul de primărie AKS este polinomial pentru zecimal (sau orice altă bază b ≥ 2 ). Testul de primărie Lucas-Lehmer este cel mai cunoscut algoritm pentru primele Mersenne M _p cu p un prim ciudat, dar este încă exponențial în lungimea codă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ă este utilizată cea mai eficientă codificare. Adică binar pentru numere întregi. (Rețineți că nu fiecare număr prim este un prim Mersenne, așa că utilizarea exponentului Mersenne nu este o schemă generală de codificare.)

În criptografie teoretică, mulți algoritmi primesc formal un șir complet inutil de k 1 s ca prim parametru. Algoritmul nu se uită niciodată la acest parametru, dar îi permite să fie formal polinomial în k , care este parametru de securitate folosit 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 -completați 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 container de ambalare .

Este, de asemenea (și poate mai mult) interesant să vezi cum complexitatea unui algoritm se modifică dacă intrarea este comprimată . Pentru exemplul primelor Mersenne, am văzut trei codificări, fiecare dintre ele fiind logaritmic mai comprimată decât predecesorul său.

În 1983, Hana Galperin și Avi Wigderson a scris o lucrare interesantă despre complexitatea algoritmilor graficului obișnuit atunci când codarea 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 „deoarece clasele de limbă precum P și NP sunt definite pentru limbi , nu pentru probleme .

Comentarii

• Acest răspuns probabil nu este util pentru nivelul de înțelegere al persoanei care întreabă. Citiți celelalte răspunsuri și vedeți cu ce se confruntă Nanako. Credeți că acest lucru răspunsul îl va ajuta?
• Este posibil ca acest răspuns să nu ajute OP, dar cu siguranță ajută și alți cititori (inclusiv eu).
• răspuns foarte util! afișat.

Voi încerca să vă dau o definiție mai puțin informală pentru același lucru.

Probleme P: probleme care pot fi rezolvate în timp polinomial. Conține probleme care pot fi rezolvate eficient.

Problemă NP: probleme care pot fi verificate în polino timpul mial. De exemplu: vânzător călător, proiectarea circuitelor. Problemele NP sunt ca niște puzzle-uri (cum ar fi sudoku). Având în vedere o soluție corectă pentru problemă, putem verifica soluția foarte repede, dar dacă încercăm să o rezolvăm, ar putea dura o veșnicie.

Acum, P vs NP întreabă dacă o problemă a cărei soluție poate fi rapidă verificat pentru a fi corect, atunci există întotdeauna o modalitate rapidă de a o rezolva. Scriind astfel în termeni matematici: este NP un subset de P sau nu?

Acum revenind la NP complet: acestea sunt problemele cu adevărat grele ale problemelor NP. Prin urmare, dacă există o modalitate mai rapidă de a rezolva NP complet, atunci NP complet devine P și problemele NP se prăbușesc în P.

NP greu: problemele care nu pot fi chiar verificate în timpul polinomului sunt np grele. De exemplu, alegerea celei mai bune mișcări în șah este una dintre ele.

Dacă ceva rămâne neclar, încercați să urmăriți acest videoclip: https://www.youtube.com/watch?v=YX40hbAHx3s

Sper că acest lucru va oferi un contur neclar.