В этой статье будут объяснены основные определения и инструменты, необходимые для понимания сложных вычислительных задач, и как даже начать подходить к ним.
Определения 1
Прежде чем заняться проблемами P, NP и т. д., мы должны понять, что такое проблема принятия решения.
Проблема решения = Проблема решения — это проблема, для которой любое предлагаемое решение может быть быстро проверено на правильность.
«проблема» = Проблема, I, например сортировка, поиск которой мы разрабатываем алгоритмы для решения.
«предлагаемое решение» = Предлагаемое решение S передается алгоритму проверки C вместе с проблемой I.
«Алгоритм проверки» = Алгоритм проверки выводит T/F или YES/NO, если предлагаемое решение S является решением проблемы I.
Все вместе:C выводит true тогда и только тогда, когда S является решением, например, I.
Время выполнения "быстро":время выполнения C на экземпляре (I,S) является полиномиальным.
Определения 2
P ("полиномиальные") проблемы = проблемы, которые решаются с помощью алгоритма за полиномиальное время. Другими словами, задача может быть решена за время выполнения n^O(1) (n возведено в константу). Это «легкие» задачи для компьютеров.
Примеры задач P:
- Самая длинная возрастающая подпоследовательность
- Двустороннее сопоставление
- Умножение
- и т. д.
NP («недетерминированные») проблемы = проблемы, которые не решаются за полиномиальное время, а являются экспоненциальными. НО проверяемы за полиномиальное время! Это более сложные проблемы
Пример NP-проблем:
- Проблема коммивояжера
- Минимальное связующее дерево
- Соответствие
- и т. д.
NP-полные проблемы = это сложно. Есть два условия, которые должны быть соблюдены, чтобы задача была NP-полной:
- Проблема X находится в NP И
- Каждая задача в NP сводится к X за полиномиальное время.
Что, черт возьми, это значит?!
Ну, это значит, что NP-полные задачи решать труднее всего.
- Задачу нельзя решить за разумное полиномиальное время. Но может случиться так, что при наличии предлагаемого решения его можно проверить за полиномиальное время.
- Задачу можно уменьшить или использовать для имитации другой задачи NP
NP-полные задачи имеют аналогичную разрешимость. Условие 2 имеет решающее значение для классификации NP по сравнению с NP-полным.
NP-сложные задачи = Проблема X является NP-сложной, если существует NP-полная задача Y, такая что Y сводится к X за полиномиальное время.
Примечание: NP-трудная задача НЕ обязательно должна быть проблемой решения. Принимая во внимание, что NP-полные проблемы - это исключительно проблемы принятия решений.
Пример:
Проблема с остановкой
Определение 3
Редукции = редукция от проблемы решения A к проблеме решения B (A⇒B) является алгоритмом с полиномиальным временем, f:
- Это преобразует экземпляр I из A в экземпляр f(I) из B.
Вместе с другим алгоритмом полиномиального времени, h:
- Это отображает любое решение S задачи f(I) обратно в решение h(S) задачи I.
Если f(I) не имеет решения, то нет и I.
По английски пожалуйста.
Итак, вся идея состоит в том, что, скажем, у вас есть проблемы A и B, которые являются NP-полными.
Если бы у вас был алгоритм, который решал задачу Б немного эффективнее, чем задачу А, несмотря на то, что это разные задачи (на первый взгляд).
Вы можете свести задачу A к задаче B, а алгоритм B можно использовать в качестве подпрограммы для решения алгоритма A!
Зачем и когда использовать сокращение?!
- Когда мы пытаемся решить проблему, а вы решили аналогичную задачу (по сути). Таким образом, вы можете преобразовать каждый экземпляр новой проблемы в экземпляры «решенной» старой проблемы. Затем, используя решения старой проблемы, получить решения новой проблемы!
- Допустим, вы доказали, что проблему трудно решить. Теперь вы представили новую проблему, похожую по сути. Таким образом, вы можете с помощью редукции доказать с помощью противоречия, что новая задача также сложна!
Если вы дошли до конца. Тогда большое спасибо за то, что нашли время, чтобы узнать что-то сложное!
Пожалуйста, дайте отзыв. Поправьте и меня, если нужно!
