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