NP (teoria complexității)

Pentru alte sensuri, vedeți NP.

Clasa de complexitate NP (nedeterminist polinomial) cuprinde problemele de decizie care sunt executate în cel mai rău caz în timp polinomial de către o mașină Turing nedeterministă. „Execuție în timp polinomial” înseamnă, în acest context, că numărul de „pași” făcuți de mașina Turing de la starea ei inițială la oricare dintre stările ei finale, acceptoare, este limitat superior de un polinom $p(n)$ de grad finit, unde $n$ este dimensiunea datelor de intrare ale problemei, și aceasta indiferent care sunt datele de intrare de dimensiune $n$. Un „pas” de execuție al mașinii Turing constă din aplicarea funcției ei de tranziție $\delta$ o dată. „În cel mai rău caz” se referă la datele de intrare: indiferent ce date de intrare de dimensiune $n$ am alege, timpul de execuție nu depășește $c\cdot p(n)$, unde $c$ este o constantă pozitivă.

În alte cuvinte, problemele din clasa NP sunt problemele de decizie al căror timp de execuție pe o mașina Turing nedeterministă are complexitatea $\scriptstyle {\mathcal {O}}(p(n))$ în cel mai rău caz, unde $p(n)$ este un polinom de grad finit.

Clasa de complexitate NP este amintită deseori in același context cu clasa de complexitate P. Aceasta din urmă cuprinde toate problemele de decizie al căror timp de execuție pe o mașină Turing deterministă are complexitatea $\scriptstyle {\mathcal {O}}(p(n))$ în cel mai rău caz, unde $p(n)$ este un polinom de grad finit. Cum mașinile Turing deterministe sunt un caz particular de mașini Turing nedeterministe, orice problemă rezolvată în timp polinomial de o mașină Turing deterministă este rezolvată în timp polinomial și de o mașină Turing nedeterministă. Deci orice problemă din clasa P aparține și clasei NP. Astfel, mulțimea P este o submulțime a mulțimii NP. Formal, $P\subseteq NP$.

Vezi și

• Mașina Turing
• Mașina Turing deterministă
• Mașina Turing nedeterministă
• Clasă de complexitate
• P (teoria complexității)