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

В теории сложности вычислений задача является NP-полной, когда:

  1. детерминированная машина Тьюринга может решить, например , с помощью алгоритма поиска перебора, и может проверить свои решения за полиномиальное время [1] и
  2. его можно использовать для моделирования любой другой задачи с аналогичной разрешимостью.

Точнее, каждый вход проблемы должен быть связан с набором решений полиномиальной длины, справедливость которых может быть быстро проверена (за полиномиальное время ) [2] , так что выход для любого входа будет «да», если решение установлено непусто и "нет", если оно пусто. Класс сложности задач этой формы называется NP , сокращение от «недетерминированное полиномиальное время». Проблема называется NP-сложной.если все в NP может быть преобразовано в него за полиномиальное время, даже если это не может быть в NP. И наоборот, проблема NP-полная, если она одновременно NP и NP-трудна. NP-полные задачи представляют собой самые сложные проблемы в NP. Если любая NP-полная задача имеет алгоритм с полиномиальным временем, то все задачи NP имеют. Набор NP-полных задач часто обозначают NP-C или NPC .

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

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

Обзор [ править ]

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

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

Формальное определение [ править ]

См. Также: формальное определение NP-полноты (статья P = NP )

Проблема решения является NP-полной, если:

  1. находится в NP, и
  2. Каждая задача в NP сводится к за полиномиальное время. [3]

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

Обратите внимание, что задача, удовлетворяющая условию 2, называется NP-сложной независимо от того, удовлетворяет она условию 1. [4]

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

Фон [ править ]

Понятие NP-полноты было введено в 1971 г. (см. Теорему Кука – Левина ), хотя термин NP-полнота был введен позже. На конференции STOC 1971 года между компьютерными учеными велись ожесточенные споры о том, можно ли решить NP-полные задачи за полиномиальное время на детерминированной машине Тьюринга . Джон Хопкрофт привел всех участников конференции к консенсусу, что вопрос о том, разрешимы ли NP-полные задачи за полиномиальное время, следует отложить до решения на более поздний срок, поскольку ни у кого не было никаких формальных доказательств своих утверждений тем или иным способом. . Это известно как «вопрос о том, P = NP».

Никто еще не смог окончательно определить, действительно ли NP-полные проблемы разрешимы за полиномиальное время, что делает эту проблему одной из величайших нерешенных проблем математики . Математический институт Clay предлагает $ 1 млн награду любому , кто имеет формальное доказательство того, что P = NP или что P ≠ NP США.

Теорема Кука – Левина утверждает, что проблема булевой выполнимости является NP-полной. В 1972 году Ричард Карп доказал, что несколько других задач также являются NP-полными (см . 21 NP-полную задачу Карпа ); таким образом, существует класс NP-полных задач (помимо проблемы булевой выполнимости). Со времени получения исходных результатов было показано, что тысячи других задач являются NP-полными, за счет сокращения других проблем, которые ранее были NP-полными; многие из этих проблем собраны в книге Гэри и Джонсона 1979 года « Компьютеры и неразрешимость: руководство по теории NP-полноты» . [5]

NP-полные задачи [ править ]

Некоторые NP-полные задачи с указанием редукций, обычно используемых для доказательства их NP-полноты
Основная статья: Список NP-полных задач

Интересный примером является проблема изоморфизма графов , то граф теории проблемы определения , является ли изоморфизм графов существует между двумя графиками. Два графа изоморфны, если один можно преобразовать в другой, просто переименовав вершины . Рассмотрим эти две проблемы:

  • Изоморфизм графов: изоморфен ли граф G 1 графу G 2 ?
  • Изоморфизм подграфов: изоморфен ли граф G 1 подграфу графа G 2 ?

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

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

  • Проблема логической выполнимости (SAT)
  • Задача о рюкзаке
  • Гамильтонова проблема пути
  • Задача коммивояжера (вариант решения)
  • Проблема изоморфизма подграфов
  • Проблема суммы подмножества
  • Проблема клики
  • Проблема покрытия вершины
  • Независимая задача набора
  • Проблема доминирующего набора
  • Задача раскраски графа

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

Часто существует лишь небольшая разница между проблемой в P и NP-полной проблемой. Например, проблема 3-выполнимости , ограничение проблемы логической выполнимости, остается NP-полной, тогда как несколько более ограниченная проблема 2-выполнимости находится в P (в частности, NL-завершена ), а немного более общая задача max. 2-сб. проблема снова NP-полная. Определение того, можно ли раскрасить граф в 2 цвета, находится в P, но в 3 цвета является NP-полным, даже если оно ограничено планарными графами . Определить, является ли граф циклом или двудольным , очень просто (в L), но нахождение максимального двудольного подграфа или максимального циклического подграфа является NP-полным. Решение задачи о рюкзаке в пределах любого фиксированного процента от оптимального решения может быть вычислено за полиномиальное время, но поиск оптимального решения является NP-полным.

Решение NP-полных задач [ править ]

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

Следующие методы могут применяться для решения вычислительных задач в целом, и они часто приводят к существенно более быстрым алгоритмам:

  • Приближение : вместо поиска оптимального решения ищите решение, которое не более чем в разы превосходит оптимальное.
  • Рандомизация : используйте случайность, чтобы получить более быстрое среднее время выполнения , и позволяйте алгоритму давать сбой с некоторой небольшой вероятностью. Примечание. Метод Монте-Карло не является примером эффективного алгоритма в этом конкретном смысле, хотя эволюционные подходы, такие как генетические алгоритмы, могут быть такими.
  • Ограничение: Ограничивая структуру входных данных (например, планарными графами), обычно возможны более быстрые алгоритмы.
  • Параметризация : часто существуют быстрые алгоритмы, если определенные параметры входа фиксированы.
  • Эвристический : алгоритм, который во многих случаях работает «достаточно хорошо», но для которого нет доказательств того, что он всегда быстр и всегда дает хороший результат. Часто используются метаэвристические подходы.

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

Полнота при разных типах редукции [ править ]

В приведенном выше определении NP-полноты термин редукция использовался в техническом смысле полиномиального сокращения многих единиц .

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

Если определить аналог NP-полноты с редукциями по Тьюрингу вместо редукций «много-один», результирующий набор проблем не будет меньше NP-полного; Вопрос о том, будет ли он больше, остается открытым.

Другой тип редукции, который также часто используется для определения NP-полноты, - это редукция «многие-единицы» в логарифмическом пространстве, которая является редукцией « многие-единицы», которую можно вычислить только с логарифмическим объемом пространства. Поскольку каждое вычисление, которое может быть выполнено в логарифмическом пространстве, также может быть выполнено за полиномиальное время, из этого следует, что если существует редукция «многие-единицы» в логарифмическом пространстве, то существует также редукция «многие-единицы» за полиномиальное время. Этот тип редукции более совершенен, чем более обычная редукция многочленов за полиномиальное время, и позволяет нам различать больше классов, таких как P-полные. Остается открытым вопрос о том, является ли определение NP-полных изменений при этих типах редукций. Все известные в настоящее время NP-полные проблемы являются NP-полными при сокращении места в журнале. Все известные в настоящее время NP-полные проблемы остаются NP-полными даже при гораздо более слабых редукциях. [6] Однако известно, что редукции AC 0 определяют строго меньший класс, чем редукции за полиномиальное время. [7]

Именование [ править ]

По словам Дональда Кнута , название «NP-полный» было популяризировано Альфредом Ахо , Джоном Хопкрофтом и Джеффри Уллманом в их знаменитом учебнике «Дизайн и анализ компьютерных алгоритмов». Он сообщает, что в соответствии с результатами проведенного им опроса теоретиков информатики , они внесли изменение в гранки доказательств для книги (с «полиномиально-полными») . [8] Среди других предложений, сделанных в опросе [9], были « Геркулесовы », «грозные», Штайглица.«сваренный вкрутую» в честь Кука, и аббревиатура Шен Линя «ПЭТ», означающая «вероятно экспоненциальное время», но в зависимости от того, каким путем идет проблема P и NP , может означать «доказуемо экспоненциальное время» или «ранее экспоненциальное время». [10]

Распространенные заблуждения [ править ]

Часто встречаются следующие заблуждения. [11]

  • «NP-полные проблемы - самые трудные из известных». Поскольку NP-полные задачи находятся в NP, время их выполнения не более чем экспоненциально. Однако некоторые задачи, например, арифметика Пресбургера, требуют больше времени . Что касается некоторых проблем, то даже было доказано, что они вообще не могут быть решены, например проблема остановки .
  • «NP-полные проблемы сложны, потому что существует так много разных решений». С одной стороны, существует множество задач, для которых пространство решений столь же велико, но их можно решить за полиномиальное время (например, минимальное остовное дерево ). С другой стороны, существуют NP-задачи с не более чем одним решением, которые являются NP-трудными при рандомизированном сокращении за полиномиальное время (см. Теорему Валианта – Вазирани ).
  • «Решение NP-полных задач требует экспоненциального времени». Во-первых, это будет означать, что P ≠ NP, что до сих пор остается нерешенным вопросом. Кроме того, некоторые NP-полные задачи на самом деле имеют алгоритмы, работающие за суперполиномиальное, но субэкспоненциальное время, такое как O (2 √ n n ). Например, задачи о независимом множестве и доминирующем множестве для плоских графов являются NP-полными, но могут быть решены за субэкспоненциальное время с помощью теоремы о плоском разделителе . [12]
  • «Каждый случай NP-полной проблемы сложен». Часто некоторые или даже большинство случаев можно легко решить за полиномиальное время. Однако, если P = NP, любой алгоритм с полиномиальным временем должен асимптотически ошибаться на более чем полиномиально многих из экспоненциально многих входов определенного размера. [13]
  • «Если P = NP, все криптографические шифры могут быть взломаны». Задачу полиномиального времени может быть очень трудно решить на практике, если степень или константы полинома достаточно велики. Например, шифры с фиксированной длиной ключа, такие как Advanced Encryption Standard , могут быть взломаны за постоянное время, пробуя каждый ключ (и, таким образом, уже известно, что они находятся в P), хотя с нынешними технологиями это время может превышать возраст Вселенная. Кроме того, теоретико-информационная безопасность предоставляет криптографические методы, которые невозможно взломать даже с неограниченной вычислительной мощностью.

Свойства [ править ]

Рассматривая проблему решения как формальный язык в некоторой фиксированной кодировке, набор NPC всех NP-полных задач не закрывается :

  • союз
  • пересечение
  • конкатенация
  • Клини звезда

Неизвестно, закрыт ли NPC при дополнении , поскольку NPC = co-NPC тогда и только тогда, когда NP = co-NP , и вопрос о том, является ли NP = co-NP открытым . [14]

См. Также [ править ]

  • Почти готово
  • Гаджет (информатика)
  • Теорема Ладнера
  • Список NP-полных задач
  • NP-жесткий
  • P = проблема NP
  • Сильно NP-полный
  • Коммивояжер (фильм, 2012)

Ссылки [ править ]

Цитаты [ править ]

  1. ^ эквивалентно: недетерминированная машина Тьюринга может решить ее за полиномиальное время
  2. ^ Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Proc. Логика, методология и философия науки II . Северная Голландия.
  3. ^ J. ван Лиувен (1998). Справочник по теоретической информатике . Эльзевир. п. 84. ISBN 978-0-262-72014-4.
  4. ^ J. ван Лиувен (1998). Справочник по теоретической информатике . Эльзевир. п. 80. ISBN 978-0-262-72014-4.
  5. ^ Гарей, Майкл Р .; Джонсон, Д. С. (1979). Виктор Клее (ред.). Компьютеры и непоколебимость: руководство по теории NP-полноты . Серия книг по математическим наукам. Сан-Франциско, Калифорния: W. H. Freeman and Co., стр.  X + 338 . ISBN 978-0-7167-1045-5. Руководство по ремонту  0519066 .
  6. ^ Agrawal, М .; Allender, E .; Рудич, Стивен (1998). «Редукции в сложности схемы: теорема об изоморфизме и теорема о разрыве». Журнал компьютерных и системных наук . 57 (2): 127–143. DOI : 10.1006 / jcss.1998.1583 . ISSN 1090-2724 . 
  7. ^ Agrawal, М .; Allender, E .; Impagliazzo, R .; Pitassi, T .; Рудич, Стивен (2001). «Снижение сложности сокращений». Вычислительная сложность . 10 (2): 117–138. DOI : 10.1007 / s00037-001-8191-1 . ISSN 1016-3328 . 
  8. ↑ Дон Кнут , Трейси Ларраби и Пол М. Робертс, « Математическое письмо», архивировано 27 августа 2010 г. в Wayback Machine, § 25, Примечания МАА № 14 , МАА, 1989 г. (также Стэнфордский технический отчет, 1987 г.).
  9. Перейти ↑ Knuth, DF (1974). «Терминологическое предложение». Новости SIGACT . 6 (1): 12–18. DOI : 10.1145 / 1811129.1811130 .
  10. ^ См. Опрос, или [1] Архивировано 7 июня 2011 г. на Wayback Machine .
  11. ↑ Болл, Филипп. «Компьютер ДНК помогает коммивояжёру» . DOI : 10.1038 / news000113-10 .
  12. ^ Берн (1990) ; Deĭneko, Klinz & Woeginger (2006) ; Дорн и др. (2005) ; Липтон и Тарьян (1980) .
  13. ^ Хемаспандра, Лос-Анджелес; Уильямс, Р. (2012). "Колонка теории сложности новостей SIGACT 76". Новости ACM SIGACT . 43 (4): 70. DOI : 10,1145 / 2421119,2421135 .
  14. ^ Талбот, Джон; Уэлш, DJA (2006), Сложность и криптография: Введение , Cambridge University Press, стр. 57, ISBN 9780521617710, Вопрос о том, равны ли NP и co-NP, вероятно, является второй по важности открытой проблемой в теории сложности после вопроса P и NP.

Источники [ править ]

  • Garey, MR ; Джонсон, Д.С. (1979). Компьютеры и непоколебимость: руководство по теории NP-полноты . Нью-Йорк: WH Freeman. ISBN 978-0-7167-1045-5. Эта классическая книга развивает теорию, а затем каталогизирует многие NP-Complete задачи.
  • Кук, SA (1971). «Сложность процедур доказательства теорем». Труды, Третий ежегодный симпозиум ACM по теории вычислений, ACM, Нью-Йорк . С. 151–158. DOI : 10,1145 / 800157.805047 .
  • Данн, ЧП "Аннотированный список избранных NP-полных задач" . COMP202, факультет компьютерных наук Ливерпульского университета . Проверено 21 июня 2008 .
  • Crescenzi, P .; Канн, В .; Halldórsson, M .; Карпинский, М .; Woeginger, G . «Сборник задач оптимизации НП» . KTH, Стокгольм . Проверено 24 октября 2020 .
  • Дальке, К. "NP-полные задачи" . Справочный проект по математике . Проверено 21 июня 2008 .
  • Карлссон, Р. "Лекция 8: NP-полные проблемы" (PDF) . Кафедра компьютерных наук, Лундский университет, Швеция. Архивировано из оригинального (PDF) 19 апреля 2009 года . Проверено 21 июня 2008 .
  • Sun, HM "Теория NP-полноты" . Лаборатория информационной безопасности, факультет компьютерных наук, Национальный университет Цин Хуа , город Синьчжу, Тайвань. Архивировано из оригинального (PPT) 2 сентября 2009 года . Проверено 21 июня 2008 .
  • Цзян, JR "Теория NP-полноты" (PPT) . Кафедра компьютерных наук и информационной инженерии, Национальный центральный университет , город Чжонли, Тайвань . Проверено 21 июня 2008 .
  • Кормен, TH ; Лейзерсон, CE ; Ривест, Р.Л . ; Стейн, К. (2001). «Глава 34: НП - Полнота». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 966–1021. ISBN 978-0-262-03293-3.
  • Сипсер, М. (1997). «Разделы 7.4–7.5 (NP-полнота, Дополнительные NP-полные задачи)» . Введение в теорию вычислений . PWS Publishing. С.  248–271 . ISBN 978-0-534-94728-6.
  • Пападимитриу, К. (1994). «Глава 9 (NP-полные задачи)». Вычислительная сложность (1-е изд.). Эддисон Уэсли. С. 181–218. ISBN 978-0-201-53082-7.
  • Вычислительная сложность игр и головоломок
  • Тетрис - это сложно даже приблизительно
  • Сапер NP-полный!
  • Берн, Маршалл (1990). «Более быстрые точные алгоритмы для деревьев Штейнера в плоских сетях». Сети . 20 (1): 109–120. DOI : 10.1002 / нетто.3230200110 ..
  • Deĭneko, Владимир Г .; Клинц, Беттина; Woeginger, Герхард Дж. (2006). «Точные алгоритмы решения проблемы гамильтонова цикла в плоских графах». Письма об исследованиях операций . 34 (3): 269–274. DOI : 10.1016 / j.orl.2005.04.013 ..
  • Дорн, Фредерик; Пеннинкс, Элко; Bodlaender, Hans L .; Фомин, Федор В. (2005). «Эффективные точные алгоритмы на плоских графах: использование разложений сферических ветвей». Proc. 13-й Европейский симпозиум по алгоритмам (ESA '05) . Конспект лекций по информатике. 3669 . Springer-Verlag. С. 95–106. DOI : 10.1007 / 11561071_11 . ISBN 978-3-540-29118-3..
  • Липтон, Ричард Дж .; Тарджан, Роберт Э. (1980). «Приложения теоремы о плоском сепараторе». SIAM Journal on Computing . 9 (3): 615–627. DOI : 10,1137 / 0209046 ..

Дальнейшее чтение [ править ]

  • Скотт Ааронсон , NP-полные проблемы и физическая реальность , ACM SIGACT News, Vol. 36, № 1. (март 2005 г.), стр. 30–52.
  • Лэнс Фортноу , Статус проблемы P по сравнению с NP , Commun. ACM , Vol. 52, № 9. (2009), стр. 78–86.