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

StackOverflow https://stackoverflow.com/questions/210829

Вопрос

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

Это было полезно?

Решение

НП расшифровывается как Недетерминированный Многочлен время.

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

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

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

Другие советы

Что такое НП?

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

Что такое P?

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

Что такое NP-Полный?

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

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

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

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

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

Что такое NP-Жесткий?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

         1) Неразрешимая задача          2) Неразрешимая задача          3) NP-задача          4) P-задача

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

P:относится к решению задачи о полиномиальном времени.

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

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

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

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

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

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

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

(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 = P, то мы можем решать очень сложные задачи гораздо быстрее, чем думали раньше.Если мы решим только одну NP-полную задачу за P (полиномиальное) время, то она может быть применена ко всем остальным задачам категории NP-полной.

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

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

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

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

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

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

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

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

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

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

Классическим примером NP-полной задачи является Задача коммивояжера."

Автор:Апоксибутт От: http://www.everything2.com/title/NP-complete

NP - проблема :-

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

Тип Np -задачи

  1. NP завершено
  2. NP Жесткий

NP-полная задача :-

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

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

Какой-то Бывший :-

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

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

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

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

Так что начинай нервничать.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top