Înțelegerea complexității NP: definiție și exemple

NP înseamnă „timp polinomial nondeterminist”. Este o clasă de complexitate care se referă la timpul necesar pentru rezolvarea unei probleme. În NP, timpul de rulare al unui algoritm poate fi polinomial în dimensiunea intrării, dar poate fi și nedeterminist, ceea ce înseamnă că timpul de rulare poate varia în funcție de soluția specifică aleasă de algoritm.

Cu alte cuvinte, NP este un clasă de probleme care pot fi rezolvate în timp polinomial pe o mașină nedeterministă. O mașină nedeterministă este o mașină care poate încerca toate soluțiile posibile la o problemă în paralel și o acceptă pe prima care funcționează. Acest lucru permite mașinii să rezolve unele probleme mult mai rapid decât o mașină deterministă, care poate încerca doar o soluție odată. găsiți cel mai scurt traseu posibil care vizitează fiecare oraș exact o dată)
* Problema rucsacului (având în vedere un set de articole și greutățile și valorile acestora, determinați subsetul de articole de inclus într-un rucsac de capacitate limitată care maximizează valoarea totală)
* Problema de satisfacție booleană (având în vedere un set de variabile booleene și constrângerile acestora, se determină dacă există o alocare de valori variabilelor care satisface toate constrângerile)

Clasa de complexitate NP este importantă deoarece include multe probleme care sunt greu de rezolvat în polinom timp, dar poate fi verificat rapid de o mașină deterministă. Aceasta înseamnă că, deși un algoritm nu poate găsi o soluție în timp polinomial, poate fi totuși util dacă poate verifica rapid o soluție propusă.