НП (класа комплексности) — разлика између измена

У [[теорија комплексности|теорији комплексности]], '''НП''' (''недетерминистичко полиномијално време'') је скуп [[проблем одлучивања|проблема одлучивања]] решивих у [[полиномијално време|полиномијалном времену]] на [[недетерминистичка Тјурингова машина|недетерминистичкој Тјуринговој машини]]. Еквивалентно, то је скуп проблема чија решења могу да се ''провере'' на [[детерминистичка Тјуринговатјурингова машина|детерминистичкој Тјуринговој машини]] у полиномијалном времену.

Пошто су многи важни проблеми у овој класи, улагани су интензивни напори да се нађу алгоритми у полиномијалном времену за проблеме у НП класи. Међутим, велики број НП проблема је одолео овим напорима, и изгледа да они захтевају суперполиномијално време. Да ли ови проблеми стварно нису решиви у полиномијалном времену је једно од највећих отворних питања у рачунарству (види '''[[п = НП проблем|класе комплексности П и НП]]''' за дубље објашњење).

Важан појам у овом контексту представља скуп [[НП-комплетанкомплетни проблемпроблеми|НП-комплетних]] проблема одлучивања, који су подскуп класе НП, и неформално се могу описати као ''најтежи'' НП проблеми. Ако би постојао алгоритам у полиномијалном времену за макар један од њих, онда би постојао полиномијални алгоритам за све проблеме из класе НП. Због овога, и зато што до сада (упркос свим напорима) није пронађен полиномијални алгоритам ни за један НП-комплетан проблем, када се за неки проблем покаже да је НП-комплетан, обично се сматра да није вероватно да постоји полиномијални алгоритам за тај проблем.