что такое np

Ответ от Dima[гуру]
NP означает nondeterministic polynomial, то есть недетерминированное полиномиальное время. Это класс вычислительных задач, правильное решение которых можно проверить за полиномиальное время. NP-трудные задачи — это задачи, к которым можно свести любую задачу из класса NP. Они как минимум так же сложны, как самые трудные задачи в NP. NP-полные задачи — это задачи, которые одновременно являются NP-трудными и принадлежат классу NP. Это самые сложные задачи внутри самого класса NP. Если для любой NP-полной задачи найдется быстрый алгоритм решения, то и все остальные задачи класса NP можно будет решать быстро.