pentru înregistrare, status quo – ul este că P≠NP.P (timp polinomial) se referă la clasa de probleme care pot fi rezolvate printr-un algoritm în timp polinomial. Problemele din clasa P pot varia de la orice la fel de simplu ca înmulțirea până la găsirea celui mai mare număr dintr-o listă. Ele sunt relativ „mai ușor” set de probleme.NP (timp polinomial nedeterminist) se referă la clasa de probleme care pot fi rezolvate în timp polinomial de către un computer nedeterminist., Acesta este, în esență, un alt mod de a spune „dacă am putere de calcul nelimitată (adică câte computere am nevoie), sunt capabil să rezolv orice problemă în cel mai mult timp polinomial”. Mai intuitiv, deși, se referă la clasa de probleme care în prezent, nu are nici o modalitate de a găsi un rapid (timp polinomial) răspuns suficient, dar poate fi rapid verificate (în timp polinomial) dacă unul oferă soluția la problema. Termenul verificat aici înseamnă că cineva poate verifica dacă soluția furnizată este într-adevăr corectă.în mod clar, pe baza definiției de mai sus, P ⊆ NP., Să aruncăm o privire la un exemplu pentru a ilustra această problemă abstractă.unul dintre cele mai comune, dar eficiente exemple este Sudoku. Având în vedere o grilă Sudoku nerezolvată (9 x 9 de exemplu), ar fi nevoie de un algoritm o cantitate corectă de timp pentru a rezolva unul. Cu toate acestea, dacă grila 9 x 9 crește la o grilă 100 x 100 sau 10,000 x 10,000, timpul necesar pentru a o rezolva ar crește exponențial, deoarece problema în sine devine semnificativ mai grea., Cu toate acestea, având în vedere o grilă Sudoku rezolvată (de 9 x 9), este destul de simplu să verificați dacă soluția particulară este într-adevăr corectă, chiar dacă dimensiunea se ridică la 10,000 cu 10,000. Ar fi mai lent, dar timpul pentru a verifica o soluție crește într-un ritm mai lent (polinomial).există multe alte probleme NP acolo, inclusiv problema rucsacului și problema vânzătorilor care călătoresc și sunt similare prin faptul că sunt greu de rezolvat, dar rapid de verificat., Problema fundamentală pe care încercăm să o rezolvăm aici este:
capacitatea de a recunoaște rapid răspunsurile corecte NP înseamnă că există și o modalitate rapidă de a le găsi?
Dacă da (adică P=NP), acest lucru ar putea schimba foarte mult modul în care privim aceste probleme NP, deoarece asta înseamnă că există o modalitate rapidă de a rezolva toate aceste probleme, doar că nu am reușit încă să ne dăm seama cum.
dacă acest lucru nu este destul de complicat, hai să-l condimentăm.,printre aceste probleme NP, există un rege al tuturor problemelor pe care cercetătorii le numesc probleme NP-Complete. Formal, ele sunt un set de probleme la fiecare dintre care orice altă problemă NP poate fi redusă (abordată mai jos) în timp polinomial și a cărei soluție poate fi încă verificată în timp polinomial. Aceasta înseamnă că orice problemă NP poate fi transformată într-o problemă completă NP.în mod informal, acestea sunt” cele mai grele ” dintre problemele NP., Astfel, dacă orice problemă NP-completă poate fi rezolvată în timp polinomial, atunci fiecare problemă NP-completă poate fi rezolvată în timp polinomial și fiecare problemă din NP poate fi rezolvată în timp polinomial (adică P=NP). Cel mai faimos exemplu ar fi problema vânzătorilor care călătoresc.
Foto de JESHOOTS.COM pe Unsplash
există, de asemenea, un set de probleme numite NP-Hard probleme., Aceste probleme sunt cel puțin la fel de grele ca problemele NP, dar fără condiția care necesită rezolvarea în timp polinomial. Acest lucru sugerează că problemele NP-Hard nu pot face neapărat parte din clasa NP. Un exemplu ar fi rezolvarea unei table de șah — având în vedere o stare a unei table de șah, este aproape imposibil de spus dacă o anumită mișcare la starea dată este de fapt mișcarea optimă. Formal, nu există un algoritm de timp polinomial pentru a verifica o soluție la o problemă NP-Hard.,dacă punem cele două împreună, o problemă NP-Complete implică faptul că este NP-Hard, dar o problemă NP-Hard nu implică faptul că este NP-Complete.
definirea NP-completitudine
o problemă L, este NP-completă dacă:
L este NP-Hard
l aparține NP
diagrama de mai jos (focalizarea pe partea stângă) ar trebui să facă lucrurile mai clare.,
P versus NP diagram (source: https://en.wikipedia.org/wiki/P_versus_NP_problem)
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
Informal, o problemă L1 poate fi redusă la o altă problemă L2 în cazul în care:
Orice instanță de L1 poate fi modelat ca un exemplu de L2
soluția pentru acestea din urmă oferă o soluție pentru fostul și vice-versa
Pentru a înțelege acest lucru în mod intuitiv, se poate crede despre ea ca atare:
Daca L1 este reductibil la L2, L1 trebuie să fie CEL mult la fel de greu ca L2. În schimb, L2 trebuie să fie cel puțin la fel de greu ca L1.
matematic, aceasta este notată ca: L1 ≤p L2 (citit ca „L1 este polinomial reductibil la L2”).,
Visual representation of above, where f represents the polynomial-time reduction algorithm (Source: Singapore Management University)
