Как NP-Hard отличается от NP? [Дубликат]

NP-полные проблемы - это те проблемы, которые являются NP-Hard и классом сложности NP. Поэтому, чтобы показать, что любая заданная задача NP-полная, вам нужно показать, что проблема как в NP, так и в NP-hard.

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

Примером недетерминированного решения проблемы k-clique было бы что-то вроде:

1) случайным образом выбрать k узлов из графика

2 ) проверить, что эти k-узлы образуют клику.

Вышеупомянутая стратегия является полиномиальной по размеру входного графа, и поэтому проблема k-clique находится в NP.

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

. Показано, что проблема NP-hard обычно включает в себя сокращение от некоторой другой NP-жесткой проблемы к вашей проблеме с использованием полиномиального отображения времени: http : //en.wikipedia.org/wiki/Reduction_ (сложность)

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

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

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

(i) проблемой решения, (ii) число решений задачи должно быть конечным и каждое решение должно быть полиномиальной длины, а (iii ), учитывая решение многочленной длины, мы должны уметь сказать, является ли ответ на проблему да / нет

. Теперь легко видеть, что может быть много NP-трудных проблем, которые не принадлежат установить NP и решить их сложнее. В качестве интуитивного примера оптимизационная версия коммивояжера, где нам нужно найти фактическое расписание, сложнее, чем версия решения коммивояжера, где нам просто нужно определить, существует ли расписание с длиной & lt; = k.

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

[/g1]

P (Полиномиальное время): Как само название предполагает, это проблемы, которые могут быть решены в полиномиальное время.

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

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

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

Это очень неформальный ответ на заданный вопрос.

Можно ли записать 3233 как произведение двух других чисел, больших 1? Есть ли способ пройти путь вокруг всех семи мостов Кенигсберга , не взяв ни одного моста дважды? Это примеры вопросов, которые имеют общую черту. Может быть неясно, как эффективно определить ответ, но если ответ «да», то есть короткое и быстрое подтверждение проверки. В первом случае нетривиальная факторизация 51; во втором - маршрут для ходьбы по мостам (установка ограничений).

Задача решения представляет собой набор вопросов с ответами «да» или «нет», которые различаются только одним параметром. Скажем, проблема COMPOSITE = {«Является n композитным»: n является целым числом} или EULERPATH = {«Имеет ли граф G путь Эйлера?»: G - конечный граф}.

Теперь некоторые проблемы решения поддаются эффективным, если не очевидным алгоритмам. Более 250 лет назад Эйлер открыл эффективный алгоритм для таких проблем, как «Семь мостов Кенигсберга».

С другой стороны, для многих проблем решения неясно, как получить ответ, но если вы знаете какую-то дополнительную информацию, очевидно, как доказать, что у вас есть ответ правильно. COMPOSITE выглядит так: Пробное деление - это очевидный алгоритм, и он медленный: чтобы умножить 10-значное число, вам нужно попробовать что-то вроде 100 000 возможных делителей. Но если, например, кто-то сказал вам, что 61 является делителем 3233, простое длинное деление - эффективный способ убедиться, что они верны.

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

Продолжается исследование алгоритмов, и все новые умные алгоритмы создаются постоянно. Проблема, которую вы, возможно, не знаете, как эффективно решить сегодня, может оказаться эффективным (если не очевидным) решением завтра. Фактически, исследователи до 2002 нашли эффективное решение для COMPOSITE! Со всеми этими достижениями, действительно нужно задаться вопросом: неужели это немного о том, чтобы иметь короткие доказательства просто иллюзию? Может быть, каждая проблема решения , которая поддается эффективным доказательствам, имеет эффективное решение? Никто не знает .

Возможно, самым большим вкладом в эту область стало открытие уникального класса проблем NP. Играя вокруг схемных моделей для расчета, Стивен Кук нашел решение проблемы разнообразия NP, которое было доказуемо труднее или труднее, чем каждой другой проблемы NP. Для эффективного решения любой другой проблемы в NP можно было бы эффективно решить задачу boolean problemability . Вскоре после этого Ричард Карп показал, что ряд других проблем решения может служить той же цели. Эти проблемы, в некотором смысле, «самые трудные» проблемы в NP, стали известны как NP-полные проблемы.

Конечно, NP - это только класс проблем решения. Многие проблемы естественно не сформулированы таким образом: «найти факторы N», «найти кратчайший путь в графе G, который посещает каждую вершину», «дать набор переменных, которые делают следующее логическое выражение истинным». Хотя можно неофициально говорить о некоторых таких проблемах как «в NP», технически это не имеет большого смысла - они не являются проблемами решения. Некоторые из этих проблем могут даже иметь такую ​​же мощность, как NP-полная проблема: эффективное решение этих проблем (без решения) приведет непосредственно к эффективному решению любой проблемы NP. Подобная проблема называется NP-hard.

Самый простой способ объяснить P v. NP и такой, не вникая в технические вопросы, - это сравнить «проблемы с текстом» с «проблемами с множественным выбором».

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

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

Теперь, если бы мы согласились с усилием, которое забирает полиномиальное время «легко», то класс P будет состоять из «простых словесных задач», а класс NP будет состоять из «простых задач множественного выбора»

Суть P v. NP заключается в следующем: «Есть ли какие-то легкие проблемы с множественным выбором, которые нелегко, как проблемы слов»? То есть существуют ли проблемы, для которых легко проверить достоверность данного ответа, но найти, что ответ с нуля трудно?

Теперь, когда мы интуитивно понимаем, что такое NP, мы должны бросить вызов нашей интуиции. Оказывается, есть «проблемы с множественным выбором», которые в некотором смысле являются самыми сложными из них: если бы можно было найти решение одной из этих «самых трудных из всех» проблем, можно было бы найти решение для ВСЕХ Проблемы с NP! Когда Кук обнаружил это 40 лет назад, это стало полной неожиданностью. Эти «самые трудные из всех» проблем известны как NP-hard. Если вы найдете «решение проблемы с текстом» для одного из них, вы автоматически найдете «решение проблем слов» для каждой проблемы «простого множественного выбора»!

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

Как я понимаю, проблема np-hard не «сложнее», чем проблема np-complete . В самом деле, по определению, каждая np-полная задача:

1. в NP
2. np-hard

[/g2]

- введение. к алгоритмам (3е) Кормен, Лейсерсон, Ривест и Штейн, стр. 1069

Я смотрю вокруг и вижу много длинных объяснений. Вот небольшая диаграмма, которая может быть полезна для суммирования:

Обратите внимание на то, как сложность увеличивается сверху вниз: любой NP может быть сведен к NP-Complete , а любой NP -Комплекс может быть сведен к NP-Hard , все в P (полиномиальное) время.

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

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

Примечания к записи Yes или No:

• * Проблема NP, которая также является P разрешима в P времени.
• ** Задача NP-Hard, которая также NP-Complete, поддаётся проверке в P времени.
• *** NP-полные проблемы (все из которых образуют подмножество NP-hard).

Я также нашел эту диаграмму весьма полезной, увидев, как все эти типы соответствуют друг другу (обратите больше внимания на левый половина диаграммы).

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

Для тех, кто считает, что вычислительная сложность - это только P и NP, - самый исчерпывающий ресурс о проблемах с вычислительной сложностью. Помимо проблем, заданных ОП, в нем перечислены примерно 500 различных классов вычислительных задач с красивыми описаниями, а также список фундаментальных исследовательских работ, описывающих класс.