np полные задачи

Ответ от Krab Вark[гуру]
Те задачи, время решения которых (количество операций для нахождения ответа) зависит от количества входных данных, как многочлен, называются принадлежащими к P-классу (polynomial) алгоритмов. Те задачи, для которых можно хотя бы проверить правильность предложенного решения за полиномиально зависящее от входных данных время, называются принадлежащими NP-классу (non-deterministic polynomial). P-класс входит в NP-класс. А NP-полные задачи - те, для которых не доказано ни то, что они не могут быть решены за полиномиальное время, ни то, что они не могут быть решены за полиномиальное время (то есть они NP, но неизвестно, может, они и P, но это не доказать) . Это целый класс задач, для которого известно, что если когда-нибудь удастся доказать, что хоть одна задача из них принадлежит классу P, то все задачи этого класса будут принадлежать классу P - но еще ни для одной задачи этого класса не удалось найти полиномиальный алгоритм решения, так что скорее всего класс NP-полных задач никогда не войдет в класс P.