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