Словосочетание недетерминированные полиномиальные, характеризующее задачи из класса NP, объясняется следующим двухшаговым подходом к их решению. ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Макконелл Д.N. Основы современных алгоритмов Изд2


Словосочетание недетерминированные полиномиальные, характеризующее задачи из класса NP, объясняется следующим двухшаговым подходом к их решению. На втором шаге проверяется, действительно ли ответ, полученный на первом шаге, является решением исходной задачи. Каждый из этих шагов по отдельности требует полиномиального времени. Хотя оба шага и полиномиальны, число обращений к ним может оказаться экспоненциальным или факториальным.

(cкачать страницу)

Смотреть книгу на libgen

Словосочетание недетерминированные полиномиальные, характеризующее задачи из класса NP, объясняется следующим двухшаговым подходом к их решению. На втором шаге проверяется, действительно ли ответ, полученный на первом шаге, является решением исходной задачи. Каждый из этих шагов по отдельности требует полиномиального времени. Хотя оба шага и полиномиальны, число обращений к ним может оказаться экспоненциальным или факториальным.