Класс сложности NP (недетерминированное полиномиальное время) (NP) — в теории вычислительной сложности – это класс, используемый для классификации проблем принятия решений. NP – это множество проблем решения, для которых экземпляры проблемы, где ответ «да», имеют доказательства, проверяемые за полиномиальное время с помощью детерминированной машины Тьюринга.
[Чесалов А. Ю. Глоссариум по искусственному интеллекту: 2500 терминов/ А. Ю. Чесалов — «Издательские решения» 2022 г., 670 стр.]