Что такое NP-Complete в информатике?

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

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

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

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

НП обозначает время Недетерминированный Полином.

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

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

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

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.

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

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

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

Некоторые примеры - проблема логической выполнимости (или СИДЕЛ) или проблема гамильтонова цикла. Известно много проблем, относящихся к классу NP.

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

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

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

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

Основная предпосылка заключается в том, что у вас есть выражение в конъюнктивная нормальная форма, которое является способом сказать, что у вас есть серия выражений, соединенных оператором 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 верны, но я подумал, что могу лирически рассуждать об их философской важности, поскольку никто еще не обратился к этой проблеме.

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

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

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

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

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

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

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

Что такое НП?

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

Что такое п?

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

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

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

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

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

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

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

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

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

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

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

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

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

В основном проблемы этого мира можно разделить на следующие категории:

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

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

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

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

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

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

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

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

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

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

1. НП завершена
2. NP Hard

Н.П. Полная проблема: -

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

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

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

• Задача о рюкзаке
• проблема суммы подмножества
• Задача о вершинном покрытии

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

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

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

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

1. Примером NP-сложной задачи, которая сложнее, чем NP, является проблема остановки.
2. Примером NP-сложной задачи, которая в равной степени сложна с NP-проблемой, является любая задача из NP-полного набора (см. Ниже).

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

Как доказать, что P = NP, и выиграть приз в размере 1000000 долларов США?
Если бы вы могли показать, что каждая проблема NP сводится к любой другой проблеме NP, тогда набор NP-Complete охватывает все наборы NP (определение NP-Complete), то есть NP-Complete = NP. Кроме того, поскольку P⊆NP, это означает, что по крайней мере одна из этих NP-Complete задач решается за полиномиальное время, что означает, что все NP-множество может быть решено за полиномиальное время. Ясно, что можно было бы заключить, что P = NP. Что ж, это всего лишь один способ доказать, что P = NP, может быть много других способов.

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