Что такое NP-полный в информатике?

429

Что такое NP-полная проблема? Почему это такая важная тема в информатике?

Claudiu
источник
5
Возможно, вас заинтересуют ответы на этот вопрос: stackoverflow.com/questions/111307/…
Дэн Дайер
1
Ну, я решил написать свой собственный ответ, потому что мне не понравилось, как представлен принятый ответ, и я включил ссылку на вопрос P = NP.
Grom
1
Есть очень хорошая лекция arsdigita по дискретной математике, которая объясняет, что такое NP-полная проблема. Первые 50 минут в основном относятся к булевой алгебре. Поэтому переходите прямо к началу 53-й минуты, если вас интересуют только понятия P, NP, NP-полноты, проблемы булевой выполнимости и редукции.
Давитенио
1
Мы никогда не узнаем, потому что при большом n он никогда не завершится;)
Пит Элвин
1
Мне очень нравится и очень рекомендую проверить это видео объяснение: youtube.com/watch?v=YX40hbAHx3s
Максим Овсяников

Ответы:

209

NP означает недетерминированное полиномиальное время.

Это означает, что проблема может быть решена за полиномиальное время с помощью недетерминированной машины Тьюринга (например, обычной машины Тьюринга, но также с недетерминированной функцией «выбора»). По сути, решение должно быть тестируемым за раз. Если это так, и известная проблема NP может быть решена с использованием данной проблемы с измененным вводом (проблема NP может быть сведена к данной проблеме), то проблема является NP завершенной.

Главное, что нужно убрать из NP-полной задачи, это то, что она не может быть решена за полиномиальное время любым известным способом. NP-Hard / NP-Complete - это способ показать, что некоторые классы проблем не могут быть решены в реальном времени.

Изменить: Как уже отмечали другие, часто есть приблизительные решения для NP-Complete проблем. В этом случае приближенное решение обычно дает границу аппроксимации с использованием специальных обозначений, которые говорят нам, насколько близко аппроксимация.

Джонатан Адельсон
источник
2
«... проблема NP может быть сведена к данной проблеме ...» - важным ограничением для сокращения является то, что оно должно быть детерминированно полиномиальным.
Рафал Доугирд
2
Обозначение O () является общей математической нотацией, используемой повсеместно: алгоритмы аппроксимации действительно задаются с точностью O () - посмотрите статью о любом алгоритме аппроксимации на arxiv.org
Ин Сяо
1
Чтобы прояснить ситуацию, проблемы NP ссылаются на недетерминированные машины Тьюринга. Пока неизвестно, можно ли решить NP-полную задачу за полиномиальное время на детерминированной машине Тьюринга.
rjzii
1
@Yuval: Просто чтобы прояснить. То, что вы имели ранее, было совершенно неправильно (если только P = NP). От вашего комментария у меня возникает ощущение, что вы думаете, что обе версии были правильными. Если нет, прошу прощения.
33
Этот ответ далеко не полный и понятный, и я не могу понять, почему у него так много голосов.
nbro
428

Что такое НП ?

NP - это совокупность всех проблем с решением (вопросов с ответом «да» или «нет»), для которых ответы «да» могут быть проверены за полиномиальное время (O (n k ), где n - размер проблемы, а k - это постоянная) детерминированной машиной Тьюринга . Полиномиальное время иногда используется как определение быстро или быстро .

Что такое П ?

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

Что такое NP-Complete ?

Задача x, которая есть в NP, также находится в NP-Complete, если и только если любая другая проблема в NP может быть быстро (т.е. за полиномиальное время) преобразована в x.

Другими словами:

  1. х находится в NP, и
  2. Каждая проблема в NP сводится к x

Итак, что делает NP-Complete настолько интересным, так это то, что если бы любая из проблем NP-Complete должна была быть решена быстро, то все проблемы NP можно было решить быстро.

Смотрите также пост Что такое "P = NP?", И почему это такой знаменитый вопрос?

Что такое NP-Hard ?

NP-Hard - это проблемы, которые, по крайней мере, такие же сложные, как самые сложные проблемы в NP. Обратите внимание, что задачи NP-Complete также являются NP-сложными. Однако не все NP-сложные проблемы являются NP (или даже проблемой решения), несмотря на то, NPчто имеют префикс. То есть NP в NP-hard не означает недетерминированное полиномиальное время . Да, это сбивает с толку, но его использование укоренилось и вряд ли изменится.

GROM
источник
4
«То есть NP в NP-hard не означает неполиномиальный» <- NP в NP-complete (или где-либо еще) также не означает неполиномиальный.
sepp2k
1
Спасибо sepp2k за исправление. Я хотел сказать, что это не означает NP (то есть недетерминированное полиномиальное время).
2010 г.
1
Я думаю, что ваш ответ упрощает столько же или больше, чем другие в этой теме. Но это все еще очень сложная проблема для меня, чтобы понять ... Думаю, именно поэтому они платят алгоритму парни большие деньги.
SoftwareSavant
3
О NP: Я думаю, что это должно быть: Проблема может быть решена с помощью недетерминированной машины Тьюринга. (nonderterministic , а не derministic)
HQT
2
@hqt То, что я написал, правильно. Обратите внимание на слово «проверено». Вы также правы, NP может быть решена за полиномиальное время с помощью недетерминированной машины Тьюринга
grom
32

NP-Complete означает нечто очень конкретное, и вы должны быть осторожны, иначе вы ошибетесь в определении. Во-первых, проблема NP - это проблема да / нет, такая, что

  1. Для каждого случая проблемы есть доказательство за полиномиальное время с ответом «да», ответ «да» или (эквивалентно)
  2. Существует алгоритм полиномиального времени (возможно, с использованием случайных переменных), который имеет ненулевую вероятность ответа «да», если ответом на экземпляр проблемы является «да» и будет говорить «нет» в 100% случаев, если ответ - нет." Другими словами, алгоритм должен иметь уровень ложноотрицательных результатов менее 100% и не должен содержать ложных срабатываний.

Задача X является NP-полной, если

  1. X находится в NP, и
  2. Для любой проблемы Y в NP есть «сокращение» от Y до X: алгоритм за полиномиальное время, который преобразует любой экземпляр Y в экземпляр X так, что ответом на экземпляр Y является «да», если и только если ответ X-instance "да".

Если X является NP-полным и существует детерминированный алгоритм за полиномиальное время, который может правильно решить все случаи X (0% ложных срабатываний, 0% ложных отрицательных результатов), то любая проблема в NP может быть решена с помощью детерминированных полиномиальных время (уменьшением до X).

До сих пор никто не придумал такой детерминистический алгоритм за полиномиальное время, но никто не доказал, что его не существует (миллион для каждого, кто может сделать что-либо: проблема P = NP ). Это не значит, что вы не можете решить конкретный случай проблемы NP-Complete (или NP-Hard). Это просто означает, что у вас не может быть чего-то, что будет надежно работать во всех случаях проблемы так же, как вы могли бы надежно отсортировать список целых чисел. Возможно, вам удастся придумать алгоритм, который будет очень хорошо работать во всех практических случаях проблемы NP-Hard.

David Nehme
источник
1
Я не люблю хвастаться, но я очень горжусь моим детерминированным алгоритмом полиномиального времени, который, как я доказал, не существует. ;)
Кайл Кронин
20
Я обнаружил поистине изумительное доказательство этого, которое этот комментарий слишком узок, чтобы его содержать;)
quick_dry
Условие № 2 - это утверждение P =? NP, а не стандартное определение NP-полноты. Должно быть: существует детерминированный многополосный алгоритм, который может преобразовать любой другой экземпляр NP NP в экземпляр Y этой проблемы, st ответ на Y - «да», если и только если ответ на X - «да».
Крис Конвей
«Вы должны быть осторожны, иначе вы получите неправильное определение», - как доказано этим самым ответом. Этот ответ отчасти верен, но его не следовало принимать.
Windows программист
29

В основном проблемы этого мира могут быть классифицированы как

         1) неразрешимая проблема 2) неразрешимая проблема 3) NP-проблема 4) P-проблема


         1) Первое - это не решение проблемы. 2) Второе - это экспоненциальное время необходимости (то есть O (2 ^ n) выше). 3) Третий называется НП. 4) Четвертая проблема легкая.


П: относится к решению проблемы полиномиального времени.

NP: относится к полиномиальному времени, чтобы найти решение. Мы не уверены, что решения за полиномиальное время не существует, но как только вы предоставите решение, это решение может быть проверено за полиномиальное время.

NP Complete: относится к полиномиальному времени, нам еще предстоит найти решение, но его можно проверить за полиномиальное время. Проблема NPC в NP - более сложная проблема, поэтому, если мы сможем доказать, что у нас есть P-решение проблемы NPC, тогда проблемы NP, которые можно найти в P-решении.

NP Hard: относится к полиномиальному времени, пока еще не найдено решение, но оно точно не может быть проверено в полиномиальном времени. NP Hard проблема превосходит NPC сложность.

Маркус Торнтон
источник
Рад видеть этот ответ, часть классификации довольно выразительна для всей концепции. Я думал, что интерактивные проблемы - это NP-проблемы.
PeerNet
22

NP-Complete - это класс задач.

Класс Pсостоит из тех задач, которые разрешимы за полиномиальное время . Например, они могут быть решены в O (n k ) для некоторой константы k, где n - размер ввода. Проще говоря, вы можете написать программу, которая будет работать в разумные сроки.

Класс NPсостоит из тех задач, которые можно проверить за полиномиальное время. То есть, если нам дано потенциальное решение, то мы можем проверить, является ли данное решение правильным за полиномиальное время.

Некоторыми примерами являются проблема булевой удовлетворенности (или SAT ) или проблема цикла Гамильтона. Есть много проблем, о которых известно, что они относятся к классу NP.

NP-Completeозначает, что проблема не менее сложна, чем любая проблема в NP.

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

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

Vincent Ramdhanie
источник
это не верно. Проблема в NP может быть преобразована в любую проблему в NP-полной, а не любую проблему в NP. Это большая разница.
Дэвид Неем
Кроме того, «проблема такая же сложная, как любая проблема в NP» - правда, но лучшая формулировка будет «по крайней мере такой же сложной». В целом, этот ответ ближе, чем любой другой ответ, который я видел, и ближе, чем, к сожалению, принятый ответ.
Windows программист
Спасибо за ваши наблюдения. Я обновил ответ, включая ваши исправления.
Винсент Рамдани
1
Ваше определение NP-Complete не является полным, вам также нужно указать, что проблемы NP-Complete также являются проблемами NP (и NP-hard), а не такими же сложными, как любые проблемы NP. Я буду понижать голос, если вы решите измениться, сообщите мне, и я уберу понижающий голос.
nbro
20

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

Для некоторых задач NP-Complete есть много хороших эвристик, но в лучшем случае они являются лишь догадкой.

Эрик Венделин
источник
Почти верно. У проблемы может быть неисчерпывающее решение, которое все еще не является полиномиальным по своей природе.
Марк Бесси
1
Хотя это не совсем верно, это достаточно близко для практического использования. В педантичном определении нет необходимости, хотя ФП, вероятно, хочет педантичное определение. Это хорошее приближение!
doug65536
18

Если вы ищете пример NP-полной проблемы, то я предлагаю вам взглянуть на 3-SAT .

Основная предпосылка состоит в том, что у вас есть выражение в конъюнктивной нормальной форме , что означает, что у вас есть серия выражений, объединенных OR, которые должны быть истинными:

(a or b) and (b or !c) and (d or !e or f) ...

Проблема 3-SAT состоит в том, чтобы найти решение, которое будет удовлетворять выражению, в котором каждое из OR-выражений имеет ровно 3 логических значения для сопоставления:

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

Решением этого может быть (a = T, b = T, c = F, d = F). Однако не было обнаружено ни одного алгоритма, который бы решал эту проблему в общем случае за полиномиальное время. Это означает, что лучший способ решить эту проблему - это по сути делать догадки и проверки методом грубой силы и пробовать разные комбинации, пока не найдете подходящую.

Особенностью проблемы 3-SAT является то, что ЛЮБУЮ NP-полную проблему можно свести к проблеме 3-SAT. Это означает, что если вы сможете найти алгоритм полиномиального времени для решения этой проблемы, то вы получите $ 1 000 000 , не говоря уже об уважении и восхищении компьютерными учеными и математиками во всем мире.

Кайл Кронин
источник
Возможно, меня смущают другие объяснения здесь, но не стоит ли это читать «ЛЮБАЯ проблема NP может быть сведена к проблеме 3-SAT за полиномиальное время». Потому что не это делает 3-SAT NP-Complete?
DubiousPusher
@ DubiousPusher Нет. Ответ гласит это правильно. Это изображение разъясняет это stackoverflow.com/a/7367561/2686502
jayeshsolanki93
14

Честно говоря, Википедия может быть лучшим местом для поиска ответа на этот вопрос.

Если NP = P, то мы можем решать очень сложные задачи гораздо быстрее, чем мы думали раньше. Если мы решим только одну задачу NP-Complete за P (полиномиальное) время, то она может быть применена ко всем другим задачам в категории NP-Complete.

оборота jjnguy
источник
6
«Если NP = P, то мы можем решать очень сложные задачи гораздо быстрее, чем мы думали раньше». -- Нет. Если NP = P, то существуют решения (существуют детерминированные алгоритмы для их решения), но нет никакой гарантии, что мы когда-нибудь узнаем, что это такое.
Windows программист
Честная точка зрения. Я думаю, что любое доказательство того, что P = NP, вероятно, будет конструктивным (например, публикация полиномиального алгоритма для 3-SAT).
Крис Конвей
10

Нам нужно разделить алгоритмы и задачи. Мы пишем алгоритмы для решения проблем, и они масштабируются определенным образом. Хотя это упрощение, давайте пометим алгоритм как «P», если масштабирование достаточно хорошее, и «NP», если это не так.

Полезно знать о проблемах, которые мы пытаемся решить, а не об алгоритмах, которые мы используем для их решения. Итак, мы скажем, что все задачи, которые имеют алгоритм масштабирования, находятся "в P". А те, у которых алгоритм плохого масштабирования, находятся "в NP".

Это означает, что множество простых задач тоже «в NP», потому что мы можем написать плохие алгоритмы для решения простых задач. Было бы хорошо узнать, какие проблемы в NP являются действительно сложными, но мы не просто хотим сказать: «Это те, для которых мы не нашли хороший алгоритм». В конце концов, я мог бы столкнуться с проблемой (назовите это X), которая, я думаю, нуждается в супер-удивительном алгоритме. Я говорю миру, что лучший алгоритм, который я мог бы придумать для решения X, плохо масштабируется, и поэтому я думаю, что X - действительно сложная проблема. Но завтра, может быть, кто-нибудь умнее меня придумает алгоритм, который решает X и находится в P. Так что это не очень хорошее определение сложных проблем.

Тем не менее, в NP есть много проблем, для которых никто не знает хорошего алгоритма. Так что, если бы я мог доказать, что X - это проблема определенного рода: такая, где хороший алгоритм для решения X также может быть использован некоторым окольным путем, чтобы дать хороший алгоритм для любой другой проблемы в NP. Что ж, теперь люди могут быть немного более убеждены в том, что X - действительно сложная проблема. И в этом случае мы называем X NP-Complete.

Том
источник
5

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

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

Но не все потеряно, если проблема, с которой вы столкнетесь, является NP Complete. Существует обширная и очень техническая область, где люди изучают алгоритмы аппроксимации, которые дадут вам гарантии того, что вы близки к решению полной задачи NP. Некоторые из них являются невероятно сильными гарантиями - например, для 3sat вы можете получить гарантию 7/8 по действительно очевидному алгоритму. Еще лучше, в действительности, есть некоторые очень сильные эвристики, которые превосходно дают отличные ответы (но не гарантируют!) На эти проблемы.

Обратите внимание, что две очень известные проблемы - изоморфизм графов и факторинг - не известны как P или NP.

Ин Сяо
источник
5

Я слышал объяснение, а именно: «NP-полнота, вероятно, является одной из наиболее загадочных идей при изучении алгоритмов.« NP »означает« недетерминированный полиномиальное время »и является названием того, что называется классом сложности, какие проблемы могут принадлежать. Важным в классе сложности NP является то, что проблемы в этом классе могут быть провереныалгоритмом полиномиального времени. В качестве примера рассмотрим проблему подсчета вещей. Предположим, на столе куча яблок. Проблема в том, сколько там яблок? Вам предоставляется возможный ответ 8. Вы можете проверить этот ответ за полиномиальное время, используя алгоритм подсчета яблок. Подсчет яблок происходит за O (n) (это обозначение Big-oh), потому что для подсчета каждого яблока требуется один шаг. Для n яблок нужно n шагов. Эта проблема в классе сложности NP.

Задача классифицируется как NP-полная, если можно показать, что она является NP-Hard и может быть проверена за полиномиальное время. Не вдаваясь слишком глубоко в обсуждение NP-Hard, достаточно сказать, что есть определенные проблемы, решения которых за полиномиальное время не были найдены. То есть требуется что-то вроде n! (n факториал) шаги для их решения. Однако, если вам дано решение проблемы NP-Complete, вы можете проверить это за полиномиальное время.

Классическим примером проблемы NP-Complete является проблема коммивояжера ».

Автор: ApoxyButt От: http://www.everything2.com/title/NP-complete

оборота лейзду
источник
2

НП Проблема: -

  1. NP-задачи - это такие задачи, которые могут быть решены за недетерминированное полиномиальное время.
  2. Недетерминированный алгоритм работает в два этапа.
  3. Стадия недетерминированного угадывания && Стадия недетерминированного подтверждения.

Тип проблемы Np

  1. НП завершен
  2. НП Хард

Н.П. Полная задача: -

1 Решение Решение A называется NP complete, если оно имеет следующие два свойства: -

  1. Он принадлежит к классу NP.
  2. Любая другая проблема в NP может быть преобразована в P за полиномиальное время.

Некоторые Ex: -

  • Рюкзак проблема
  • проблема подмножества сумм
  • Проблема покрытия вершин
HeadAndTail
источник
Быстрый вопрос о ваших этапах ... не может ли этап проверки быть детерминированным? Не были ли проблемы NP проверены в P-time
Бранден Кек
1

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

Джамал Хуссейн
источник
1

Насколько я понимаю

P - это множество задач, которые можно решить за полиномиальное время с помощью детерминированной TM.

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

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

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

Пожалуйста, дайте мне знать, если я сделал какую-либо ошибку.

rsonx
источник
-17

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

проблема NP-Complete - это NP, но также, если вы можете решить ее за полиномиальное время (называемое P), тогда все проблемы NP - P.

Так что взломай.

оборота Кит Твомбли
источник