NP-полнота

Класс сложности

Булева проблема выполнимости (SAT) требует определить, может ли пропозициональная формула (изображенный пример) стать истинной путем соответствующего присвоения («решения») значений истинности ее переменным. Хотя легко проверить, делает ли данное присваивание формулу истинной , ^[1] не известен существенно более быстрый метод поиска удовлетворяющего присваивания, чем перебор всех присваиваний подряд. Кук и Левин доказали, что любую легко проверяемую задачу можно решить так же быстро, как SAT, который, следовательно, является NP-полным.

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

1. Это проблема решения , что означает, что для любого входа в задачу выходом будет либо «да», либо «нет».
2. Когда ответ «да», это можно продемонстрировать через существование короткого (полиномиальной длины) решения .
3. Правильность каждого решения можно проверить быстро (а именно, за полиномиальное время ), а алгоритм поиска методом перебора может найти решение, перепробовав все возможные решения.
4. Эту задачу можно использовать для моделирования любой другой задачи, для которой мы можем быстро проверить правильность решения. В этом смысле NP-полные задачи — самые сложные из задач, решения которых можно быстро проверить. Если бы мы могли быстро найти решения некоторой NP-полной задачи, мы могли бы быстро найти решения любой другой задачи, для которой данное решение можно легко проверить.

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

Точнее, каждый вход задачи должен быть связан с набором решений полиномиальной длины, достоверность каждого из которых может быть быстро проверена (за полиномиальное время ), ^[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-полной ^{, если :} ${\displaystyle \scriptstyle C}$

1. ${\displaystyle \scriptstyle C}$находится в NP, и
2. Любая задача в NP сводится к полиномиальному времени. ^[3] ${\displaystyle \scriptstyle C}$

${\displaystyle \scriptstyle C}$можно показать, что она находится в NP, продемонстрировав, что возможное решение может быть проверено за полиномиальное время. ${\displaystyle \scriptstyle C}$

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

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

Фон

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

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

Никто еще не смог окончательно определить, действительно ли NP-полные проблемы могут быть решены за полиномиальное время, что делает эту задачу одной из величайших нерешенных проблем математики . Институт математики Клея предлагает вознаграждение в размере 1 миллиона долларов США каждому, кто предоставит формальное доказательство того, что P=NP или что P≠NP. ^[5]

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

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-полным.

Промежуточные проблемы

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

• Изоморфизм графа: изоморфен ли граф G ₁ графу G ₂ ?
• Изоморфизм подграфа: изоморфен ли граф G ₁ подграфу графа G ₂ ?

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

Решение NP-полных задач

В настоящее время все известные алгоритмы решения NP-полных задач требуют времени, суперполиномиального по размеру входных данных. Проблема вершинного покрытия имеет ^[6] для некоторых , и неизвестно, существуют ли более быстрые алгоритмы. ${\displaystyle O(1.2738^{k}+nk)}$ ${\displaystyle k>0}$

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

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

Одним из примеров эвристического алгоритма является субоптимальный алгоритм жадной окраски, используемый для раскраски графов на этапе выделения регистров некоторых компиляторов, метод, называемый глобальным распределением регистров раскраски графов . Каждая вершина является переменной, ребра рисуются между переменными, которые используются одновременно, а цвета указывают регистр, присвоенный каждой переменной. Поскольку большинство RISC- машин имеют довольно большое количество регистров общего назначения, для этого приложения эффективен даже эвристический подход. ${\displaystyle O(n\log n)}$

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

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

Другой тип сокращения — это сокращение Тьюринга за полиномиальное время. Задача сводится к задаче по Тьюрингу за полиномиальное время, если для заданной подпрограммы, которая решается за полиномиальное время, можно написать программу, которая вызывает эту подпрограмму и решает за полиномиальное время. Это контрастирует со сводимостью «многие к одному», которая имеет ограничение: программа может вызвать подпрограмму только один раз, а возвращаемое значение подпрограммы должно быть возвращаемым значением программы. ${\displaystyle \scriptstyle X}$ ${\displaystyle \scriptstyle Y}$ ${\displaystyle \scriptstyle Y}$ ${\displaystyle \scriptstyle X}$

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

Другой тип сокращения, который также часто используется для определения NP-полноты, - это сокращение «много-один» в логарифмическом пространстве , которое представляет собой сокращение «многие-один», которое можно вычислить только с логарифмическим объемом пространства. Поскольку каждое вычисление, которое может быть выполнено в логарифмическом пространстве, также может быть выполнено за полиномиальное время, из этого следует, что если существует сокращение «много-один» в логарифмическом пространстве, то существует также сокращение «многие-один» за полиномиальное время. Этот тип сокращения является более точным, чем более обычные сокращения «много-единица» за полиномиальное время, и позволяет нам различать больше классов, таких как P-complete . Вопрос о том, будет ли при таких видах редукций определение NP-полных изменений, остается открытым вопросом. Все известные в настоящее время NP-полные задачи являются NP-полными при сокращении пространства журнала. Все известные на данный момент NP-полные задачи остаются NP-полными даже при гораздо более слабых редукциях, таких как редукции и редукции. Известно, что некоторые NP-полные задачи, такие как SAT, являются полными даже при полилогарифмических временных проекциях. ^[7] Однако известно, что сокращения AC определяют строго меньший класс, чем сокращения за полиномиальное время. ^[8] ${\displaystyle AC_{0}}$ ${\displaystyle NC_{0}}$

Именование

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

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

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

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

Характеристики

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

• союз
• пересечение
• конкатенация
• Звезда Клини ^{[ нужен пример ]}

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

Смотрите также

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

Рекомендации

Цитаты

1. Например, простое присвоение true каждой переменной делает 18-е соединение (и, следовательно, всю формулу) ложным . ${\displaystyle {\overline {m}}\lor {\overline {r}}\lor {\overline {s}}}$
2. Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Учеб. Логика, методология и философия науки II . Северная Голландия.
3. Дж. ван Леувен (1998). Справочник по теоретической информатике . Эльзевир. п. 84. ИСБН 978-0-262-72014-4.
4. Дж. ван Леувен (1998). Справочник по теоретической информатике . Эльзевир. п. 80. ИСБН 978-0-262-72014-4.
5. Кирш, Энди. «Выдающийся математик утверждает, что разгадал одну из величайших загадок математики — и это одна из 6 задач с призом в 1 миллион долларов». Бизнес-инсайдер . Проверено 24 апреля 2023 г.
6. Чен, Цзянер; Кандж, Ияд А.; Ся, Гэ (6 сентября 2010 г.). «Улучшены верхние границы покрытия вершин». Теоретическая информатика . 411 (40): 3736–3756. дои : 10.1016/j.tcs.2010.06.026 . ISSN  0304-3975.
7. Агравал, М .; Аллендер, Э.; Рудич, Стивен (1998). «Снижение сложности схемы: теорема об изоморфизме и теорема о пробеле». Журнал компьютерных и системных наук . 57 (2): 127–143. дои : 10.1006/jcss.1998.1583 . ISSN  1090-2724.
8. Агравал, М .; Аллендер, Э.; Импальяццо, Р.; Питасси, Т .; Рудич, Стивен (2001). «Снижение сложности сокращений». Вычислительная сложность . 10 (2): 117–138. дои : 10.1007/s00037-001-8191-1. ISSN  1016-3328. S2CID  29017219.
9. Дон Кнут , Трейси Ларраби и Пол М. Робертс, Математическое письмо. Архивировано 27 августа 2010 г. в Wayback Machine § 25, Примечания MAA № 14 , MAA, 1989 (также Стэнфордский технический отчет, 1987).
10. Кнут, Д.Ф. (1974). «Терминологическое предложение». Новости СИГАКТ . 6 (1): 12–18. дои : 10.1145/1811129.1811130. S2CID  45313676.
11. См. опрос или [1]. Архивировано 7 июня 2011 г. на Wayback Machine .
12. Болл, Филип (2000). «ДНК-компьютер помогает коммивояжёру». Природа . дои : 10.1038/news000113-10.
13. Берн (1990); Дейнеко, Клинц и Вегингер (2006); Дорн и др. (2005) ; Липтон и Тарьян (1980).Ошибка harvtxt: нет цели: CITEREFDornPenninksBodlaenderFomin2005 ( справка )
14. Хемаспаандра, Луизиана; Уильямс, Р. (2012). «Колонка 76 теории сложности новостей SIGACT» . Новости ACM SIGACT . 43 (4): 70. дои : 10.1145/2421119.2421135. S2CID  13367514.
15. Ааронсон, Скотт (2010). «BQP и полиномиальная иерархия». В Шульмане, Леонард Дж. (ред.). Материалы 42-го симпозиума ACM по теории вычислений, STOC 2010, Кембридж, Массачусетс, США, 5–8 июня 2010 г. Ассоциация вычислительной техники. стр. 141–150. arXiv : 0910.4698 . дои : 10.1145/1806689.1806711.
16. Талбот, Джон; Уэлш, DJA (2006), Сложность и криптография: введение, Cambridge University Press, стр. 57, ISBN 9780521617710Вопрос о том, равны ли NP и co-NP, вероятно, является второй по важности открытой проблемой в теории сложности после вопроса P и NP .

Источники

• Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455. МР  0519066. OCLC  247570676.Эта книга представляет собой классику, в которой развивается теория, а затем каталогизируется множество NP-полных проблем.
• Кук, С.А. (1971). «Сложность процедур доказательства теорем». Труды Третьего ежегодного симпозиума ACM по теории вычислений, ACM, Нью-Йорк . стр. 151–158. дои : 10.1145/800157.805047 .
• Данн, PE «Аннотированный список избранных NP-полных задач». COMP202, факультет компьютерных наук, Ливерпульский университет . Проверено 21 июня 2008 г.
• Крещенци, П.; Канн, В.; Халлдорссон, М.; Карпински, М .; Вегингер, Г. «Сборник задач оптимизации NP». КТХ, Стокгольм . Проверено 24 октября 2020 г.
• Дальке, К. «NP-полные задачи». Справочный проект по математике . Проверено 21 июня 2008 г.
• Карлссон, Р. «Лекция 8: NP-полные задачи» (PDF) . Кафедра компьютерных наук Лундского университета, Швеция. Архивировано из оригинала (PDF) 19 апреля 2009 г. Проверено 21 июня 2008 г.
• Сан, Х.М. «Теория NP-полноты». Лаборатория информационной безопасности, факультет компьютерных наук, Национальный университет Цин Хуа , город Синьчжу, Тайвань. Архивировано из оригинала (PPT) 2 сентября 2009 г. Проверено 21 июня 2008 г.
• Цзян Дж.Р. «Теория NP-полноты» (PPT) . Кафедра компьютерных наук и информационной инженерии, Национальный центральный университет , город Джонли, Тайвань . Проверено 21 июня 2008 г.
• Кормен, TH ; Лейзерсон, CE ; Ривест, РЛ ; Штейн, К. (2001). «Глава 34: NP – Полнота». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 966–1021. ISBN 978-0-262-03293-3.
• Сипсер, М. (1997). «Разделы 7.4–7.5 (NP-полнота, Дополнительные NP-полные задачи)» . Введение в теорию вычислений . Издательство ПВС. стр. 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. дои : 10.1002/net.3230200110..
• Дейнеко Владимир Георгиевич; Клинц, Беттина; Вегингер, Герхард Дж. (2006). «Точные алгоритмы решения гамильтоновой задачи цикла в плоских графах». Письма об исследованиях операций . 34 (3): 269–274. дои : 10.1016/j.orl.2005.04.013..
• Дорн, Фредерик; Пеннинккс, Элко; Бодлендер, Ганс Л .; Фомин, Федор В. (2005). «Эффективные точные алгоритмы на плоских графах: использование разложения ветвей с разрезом по сфере». Учеб. 13-й Европейский симпозиум по алгоритмам (ESA '05) . Конспекты лекций по информатике. Том. 3669. Шпрингер-Верлаг. стр. 95–106. дои : 10.1007/11561071_11. ISBN 978-3-540-29118-3..
• Липтон, Ричард Дж .; Тарьян, Роберт Э. (1980). «Применение теоремы о плоском сепараторе». SIAM Journal по вычислительной технике . 9 (3): 615–627. дои : 10.1137/0209046. S2CID  12961628..

дальнейшее чтение

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