Эта задача была сформулирована в 1971 году и до сих пор остается нерешенной. За доказательство утверждения P=NP или за доказательство его опровержения Математическим институтом Клэя назначена премия в 1 миллион долларов США. Если все-таки окажется, что P=NP, то это даст возможность быстро и эффективно решать множество трудноразрешимых на данный момент задач.
Так в чем же все-таки суть проблемы?
Понятия классов сложности P и NP изучаются теорией сложности вычислений. К классу P (Polynomial time) относятся простые задачи, которые можно решить за полиномиальное время по отношению к длине ввода. Примером такой задачи может служить сортировка массива. В зависимости от выбранного алгоритма сортировки, для массива длиной n, количество выполненных операций будет от O(n*log(n)) до O(n2). Таким образом, простота алгоритмов, принадлежащих к классу P заключается в том, что при увеличении длины ввода, время выполнения увеличивается незначительно.
К классу NP (Non-deterministic Polynomial time) относятся задачи для которых проверку решения можно осуществить за полиномиальное время. Заметьте, что речь идет лишь о проверке уже найденного решения. Сложность задач этого класса заключается в том, что непосредственно нахождение решения требует значительно большего, чем полиномиальное, времени. Рассмотрим в качестве примера задачу о сумме подмножеств. Она формулируется следующим образом: «в данном множестве целых чисел, имеется ли хотя бы одно непустое подмножество сумма элементов которого равняется нулю?» Например пусть нам дано множество {5, -2, 17, 10, -4, -8}. Для него ответ на поставленный вопрос "да", поскольку искомое подмножество существует: -2+10-8=0. Легко убедиться, что проверка решения осуществляется быстро (нужно лишь просуммировать элементы найденного подмножества). Но на поиск решения необходимо затратить экспоненциальное время, поскольку необходимо проверить все возможные подмножества. Количество возможных комбинаций составляет 2n для ввода длиной n. Это делает решение поставленной задачи непрактичным для больших значений n.
Итак, возвращаемся непосредственно к проблеме P=NP. Положительный ответ будет означать, что возможно выполнение NP алгоритмов за полиномиальное время. Если это будет доказано, к примеру, для приведенной выше задачи о сумме подмножеств, то тоже самое будет справедливо и для многих других сложных задач. Дело в том, что существует особый класс NP алгоритмов, называемый NP-complete для которого доказано, что любая задача принадлежащая к нему может быть легко сведена к любой другой задаче этого класса. Вот список некоторых известных NP-complete задач:
В заключение можно сказать, что хотя вопрос о равенстве классов P и NP до сих пор не решен, многие специалисты склонны считать, что они не равны. В поддержку этого мнения приводится довод, что уже на протяжении более чем трех с половиной десятилетий не было найдено алгоритма с полиномиальным временем выполнения ни для одной из 3000 известных NP-complete задач. Но окончательно точку в споре поставит лишь строгое математическое доказательство.
Так в чем же все-таки суть проблемы?
Понятия классов сложности P и NP изучаются теорией сложности вычислений. К классу P (Polynomial time) относятся простые задачи, которые можно решить за полиномиальное время по отношению к длине ввода. Примером такой задачи может служить сортировка массива. В зависимости от выбранного алгоритма сортировки, для массива длиной n, количество выполненных операций будет от O(n*log(n)) до O(n2). Таким образом, простота алгоритмов, принадлежащих к классу P заключается в том, что при увеличении длины ввода, время выполнения увеличивается незначительно.
К классу NP (Non-deterministic Polynomial time) относятся задачи для которых проверку решения можно осуществить за полиномиальное время. Заметьте, что речь идет лишь о проверке уже найденного решения. Сложность задач этого класса заключается в том, что непосредственно нахождение решения требует значительно большего, чем полиномиальное, времени. Рассмотрим в качестве примера задачу о сумме подмножеств. Она формулируется следующим образом: «в данном множестве целых чисел, имеется ли хотя бы одно непустое подмножество сумма элементов которого равняется нулю?» Например пусть нам дано множество {5, -2, 17, 10, -4, -8}. Для него ответ на поставленный вопрос "да", поскольку искомое подмножество существует: -2+10-8=0. Легко убедиться, что проверка решения осуществляется быстро (нужно лишь просуммировать элементы найденного подмножества). Но на поиск решения необходимо затратить экспоненциальное время, поскольку необходимо проверить все возможные подмножества. Количество возможных комбинаций составляет 2n для ввода длиной n. Это делает решение поставленной задачи непрактичным для больших значений n.
Итак, возвращаемся непосредственно к проблеме P=NP. Положительный ответ будет означать, что возможно выполнение NP алгоритмов за полиномиальное время. Если это будет доказано, к примеру, для приведенной выше задачи о сумме подмножеств, то тоже самое будет справедливо и для многих других сложных задач. Дело в том, что существует особый класс NP алгоритмов, называемый NP-complete для которого доказано, что любая задача принадлежащая к нему может быть легко сведена к любой другой задаче этого класса. Вот список некоторых известных NP-complete задач:
- Задача коммивояжёра
- Задача о сумме подмножеств
- Задача выполнимости булевой формулы
- Задача о раскраске графа
- Задача о рюкзаке
В заключение можно сказать, что хотя вопрос о равенстве классов P и NP до сих пор не решен, многие специалисты склонны считать, что они не равны. В поддержку этого мнения приводится довод, что уже на протяжении более чем трех с половиной десятилетий не было найдено алгоритма с полиномиальным временем выполнения ни для одной из 3000 известных NP-complete задач. Но окончательно точку в споре поставит лишь строгое математическое доказательство.