Понимание сложности NP: определение и примеры

NP означает «недетерминированное полиномиальное время». Это класс сложности, который обозначает количество времени, необходимое для решения проблемы. В NP время работы алгоритма может быть полиномиальным по размеру входных данных, но оно также может быть недетерминированным, что означает, что время работы может варьироваться в зависимости от конкретного решения, выбранного алгоритмом. Другими словами, NP - это класс задач, которые можно решить за полиномиальное время на недетерминированной машине. Недетерминированная машина — это машина, которая может параллельно пробовать все возможные решения проблемы и принимать первое из них, которое сработает. Это позволяет машине решать некоторые проблемы намного быстрее, чем детерминированная машина, которая может пробовать только одно решение за раз. найти кратчайший возможный маршрут, который посещает каждый город ровно один раз)
* Задача о рюкзаке (дан набор предметов, их вес и ценность, определить подмножество предметов, которые нужно включить в рюкзак ограниченной вместимости, который максимизирует общую ценность)
* Проблема логической выполнимости (при наличии набора логических переменных и их ограничений определить, существует ли присвоение значений переменным, которое удовлетворяет всем ограничениям)

Класс сложности NP важен, поскольку он включает в себя множество задач, которые трудно решить полиномиально время, но может быть быстро проверено детерминированной машиной. Это означает, что даже если алгоритм не сможет найти решение за полиномиальное время, он все равно может быть полезен, если сможет быстро проверить предложенное решение.