Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
м r2.7.1) (Робот додаје: ro:NP (teoria complexității)
Ред 30:
Пошто су многи важни проблеми у овој класи, улагани су интензивни напори да се нађу алгоритми у полиномијалном времену за проблеме у НП класи. Међутим, велики број НП проблема је одолео овим напорима, и изгледа да они захтевају суперполиномијално време. Да ли ови проблеми стварно нису решиви у полиномијалном времену је једно од највећих отворних питања у рачунарству (види '''[[класе комплексности П и НП]]''' за дубље објашњење).
 
Важан појам у овом контексту представља скуп [[НП-комплетан проблем|НП-комплетхинкомплетних]] проблема одлучивања, који су подскуп класе НП, и неформално се могу описати као ''најтежи'' НП проблеми. Ако би постојао алгоритам у полиномијалном времену за макар један од њих, онда би постојао полиномијални алгоритам за све проблеме из класе НП. Због овога, и зато што до сада (упркос свим напорима) није пронађен полиномијални алгоритам ни за један НП-комплетан проблем, када се за неки проблем покаже да је НП-комплетан, обично се сматра да није вероватно да постоји полиномијални алгоритам за тај проблем.
 
== Пример ==
Преузето из „https://sr.wikipedia.org/wiki/НП_(класа_комплексности)”