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

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