Рубрики

НП-Полнота | Комплект 1 (Введение)

Мы писали об эффективных алгоритмах для решения сложных задач, таких как кратчайший путь , граф Эйлера , минимальное остовное дерево и т. Д. Это были истории успеха разработчиков алгоритмов. В этом посте обсуждаются неудачные истории информатики.

Могут ли все вычислительные проблемы быть решены с помощью компьютера? Существуют вычислительные проблемы, которые не могут быть решены алгоритмами даже при неограниченном времени. Например, проблема остановки Тьюринга (учитывая программу и входные данные, будет ли программа в конечном итоге остановлена при запуске с этим входом или будет работать вечно). Алан Тьюринг доказал, что общего алгоритма для решения проблемы остановки для всех возможных пар программ-ввода не может быть. Ключевой частью доказательства является то, что машина Тьюринга использовалась как математическое определение компьютера и программы (Source Halting Problem ).
Состояние проблем с NP Complete — это еще одна история неудач, проблемы с NP Complete — это проблемы, статус которых неизвестен. Ни один алгоритм за полиномиальное время еще не был обнаружен ни для одной полной задачи NP, и никому еще не удалось доказать, что ни для одного из них не существует алгоритма за полиномиальное время. Интересным моментом является то, что если любая из полных задач NP может быть решена за полиномиальное время, то все они могут быть решены.

Что такое проблемы NP , P , NP-complete и NP-Hard ?
Р множество проблем , которые могут быть решены с помощью детерминированной машины Тьюринга в Р olynomial времени.

НП множество проблем принятия решений , которые могут быть решены с помощью N на детерминированной машине Тьюринга в Р olynomial времени. P является подмножеством NP (любая проблема, которая может быть решена детерминированной машиной за полиномиальное время, также может быть решена недетерминированной машиной за полиномиальное время).
Неформально, NP — это набор задач для решения, которые могут быть решены за полиномиальное время с помощью «Алгоритма Лаки», магического алгоритма, который всегда делает правильное предположение среди данного набора вариантов (Источник № 1 ).

NP-полные проблемы — самые сложные проблемы в наборе NP . Решение задачи L является NP-полным, если:
1) L находится в NP (Любое данное решение для NP-полных задач может быть проверено быстро, но не существует эффективного известного решения).
2) Каждая задача в NP сводится к L за полиномиальное время (редукция определена ниже).

Проблема NP-Hard, если она следует за свойством 2, упомянутым выше, не должна следовать за свойством 1. Следовательно, NP-Complete также является подмножеством NP-Hard набора.

Решение против проблем оптимизации
NP-полнота относится к области решения проблем. Он был настроен таким образом, потому что сравнивать сложность решения проблем проще, чем проблем оптимизации. В действительности, тем не менее, способность решать проблему решения за полиномиальное время часто позволяет нам решать соответствующую задачу оптимизации за полиномиальное время (используя полиномиальное количество обращений к проблеме решения). Таким образом, обсуждение сложности проблем решения часто действительно эквивалентно обсуждению сложности задач оптимизации. (Источник № 2 ).
Например, рассмотрим задачу покрытия вершин (для заданного графа найдите множество вершин минимального размера, охватывающее все ребра). Это проблема оптимизации. Соответствующая проблема решения для заданного неориентированного графа G и k есть ли покрытие вершин размера k?

Что такое сокращение?
Пусть L 1 и L 2 — две проблемы решения. Предположим, что алгоритм A 2 решает L 2 . То есть, если y является входом для L 2, тогда алгоритм A 2 ответит Да или Нет в зависимости от того, принадлежит ли y L 2 или нет.
Идея состоит в том, чтобы найти преобразование из L 1 в L 2, чтобы алгоритм A 2 мог быть частью алгоритма A 1 для решения L 1 .

Сокращение обучения в целом очень важно. Например, если у нас есть библиотечные функции для решения определенной проблемы и если мы можем свести новую проблему к одной из решенных проблем, мы сэкономим много времени. Рассмотрим пример задачи, в которой мы должны найти минимальный путь продукта в данном ориентированном графе, где продукт пути — это умножение весов ребер вдоль пути. Если у нас есть код для алгоритма Дейкстры, чтобы найти кратчайший путь, мы можем взять журнал всех весов и использовать алгоритм Дейкстры, чтобы найти минимальный путь продукта, вместо того, чтобы писать новый код для этой новой задачи.

Как доказать, что данная задача является NP-полной?
Из определения NP-полной кажется невозможным доказать, что задача L является NP-полной. По определению требуется, чтобы мы показали, что каждая проблема в NP сводится за полиномиальное время к L. К счастью, существует альтернативный способ доказать это. Идея состоит в том, чтобы взять известную задачу NP-Complete и свести ее к L. Если полиномиальное сокращение времени возможно, мы можем доказать, что L NP-Complete, транзитивностью редукции (если задача NP-Complete сводится к L в полиноме время, то все проблемы сводятся к L за полиномиальное время).

Какая была первая проблема, доказанная как NP-Complete?
Должна быть какая-то первая проблема NP-Complete, доказанная определением задач NP-Complete. SAT (проблема булевой выполнимости) является первой NP-полной задачей, доказанной Кук (доказательство см. В книге CLRS).

Всегда полезно знать о NP-полноте даже для инженеров. Предположим, вас попросили написать эффективный алгоритм для решения чрезвычайно важной проблемы для вашей компании. После долгих размышлений вы можете придумать только экспоненциальный временной подход, который нецелесообразен. Если вы не знаете о NP-полноте, вы можете только сказать, что я не мог прийти с эффективным алгоритмом. Если вы знаете о NP-полноте и докажете, что проблема является NP-полной, вы с гордостью можете сказать, что решение за полиномиальное время вряд ли существует. Если возможно решение за полиномиальное время, то это решение решает большую проблему компьютерных наук, которую многие ученые пытались решать годами.

Вскоре мы будем обсуждать другие проблемы NP-Complete и их доказательства NP-завершенности.

Ссылки:
MIT Видео-лекция по вычислительной сложности
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест
http://www.ics.uci.edu/~eppstein/161/960312.html

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

НП-Полнота | Комплект 1 (Введение)

0.00 (0%) 0 votes