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

Садржај обрисан Садржај додат
Спашавам 1 извора и означавам 0 мртвим. #IABot (v2.0beta8)
→‎Увод и примене: Promenjen agloritam u algoritam. Mala greška u pisanju.
Ред 4:
Важност ове класе проблема одлучивања је у томе што садржи многе интересантне проблеме претраге и оптимизације, где желимо да утврдимо да ли постоји одређено решење за одређени проблем.
 
Посматрајмо на пример проблем утврђивања да ли је ''-{n}-'' [[сложен број]]. За овај проблем знамо (мада тек од 2002.) да је решив у полиномијалном времену. Међутим, аглоритамалгоритам који га решава ([[АКС тест простости]]) је и даље врло тежак. Са друге стране, ако смо нашли број за који верујемо да може бити делилац за ''-{n}-'', следећа функција нам врло брзо може рећи да ли је тај број стварно делилац, што би значило да је ''-{n}-'' сложен:
-{
''boolean'' isNontrivialFactor(''n'', ''d'')