Почему задача перебора всех вариантов принадлежит к классу NP-полных задач?

Рейтинг: 1Ответов: 1Опубликовано: 02.12.2014

Насколько мне известно, NP-класс - это такой класс задач, решение которых нельзя найти за полниномиальное время (отсюда NP - non-polynomial), такие задачи можно решить только на несуществующей реально, абстрактной машине.

Однако же задача перебора всех вариантов - это, как по мне, вполне себе задача, которая прекрасно решается за полниномиальное время.

Так почему же ее относят к классу NP-задач?

алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 2Принят

NP — это не «non-polynomial»! NP значит non-deterministic polynomial, решается за полиномиальное время, но на недетерминистской машине Тьюринга. То, что они не решаются за полиномиальное время, есть (недоказанная) гипотеза P != NP.

(Раз уж мой комментарий превратился в ответ...)

Это зависит от того, какие бывают варианты. Например, если у вас параметр задачи — размер множества M, а вариантами являются его подмножества. Тогда у вас всего 2^M вариантов, то есть, экспоненциальное количество.

Или если у вас параметром является количество разрядов числа, а вы перебираете все числа. Количество N-разрядных чисел — 2^N, то есть, снова экспонента.

(Экспонента не есть полином т. к. lim (x -> infinity) x^p/e^x = 0 для любого p.)