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