Преглед садржаја:
- Дефиниција - Шта значи неодређено полиномно време (НП)?
- Техопедија објашњава неодређено полиномно време (НП)
Дефиниција - Шта значи неодређено полиномно време (НП)?
Неодређено полиномно време (НП) је заправо маркер који се користи да укаже на скуп проблема и граница способности одређених врста рачунања. НП се односи на скуп проблема који могу да се реше у полиномном времену не-детерминирајућом Туринговом машином.
Техопедија објашњава неодређено полиномно време (НП)
Неодређено полиномно време заснива се на изразу "полиномско време", које се односи на то да ли алгоритам може да ради у одређеним границама релевантним за брзину. Полиномно време појавило се као начин да се разговара о изводљивости рада и развоја алгоритама.
Ако је проблем у неодређеном полиномском времену, недетерминистичка Турингова машина може прво погодити решење, а затим покренути верификовани алгоритам који ће потврдити да ли је та претпоставка тачна или не. Програми који се заснивају на верификатору или програми машинске дефиниције у основи ће тестирати почетне изборе недетерминистичке Турингове машине за верификацију резултата.
Све ово је високо теоријска структура рачунара. Иако је машинско учење напредовало надилазећи детерминиране системе, идеја о верификовању неопредјељених избора још је увијек у повојима. Потражите већи развој на овој граници рачунања.
