NP –полнота — в теории вычислительной сложности является проблема NP-полной, когда она может быть решена ограниченным классом алгоритмов перебора и может быть другая проблема с помощью аналогичного алгоритма. Точнее, каждый вход должен быть связан с набором решений полиномиальной длины, достоверность которого можно быстро проверить (за полиномиальное время), так что выход для любого входа будет «да», если набор решенийуст и «нет», если он пуст.
[Глоссарий искусственного интеллекта. (Электронный ресурс). Режим доступа: http:// hrwiki.ru›wiki/Glossary_of_artificial_intelligence/, свободный.]