Список NP-полных задач

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

Графики и гиперграфы [ править ]

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

1-планарность ^[1]
3-мерное сопоставление ^[2]^[3]^{: СП1}
Проблема с пропускной способностью ^[3]^{: GT40}
Двустороннее измерение ^[3]^{: GT18}
Емкостное минимальное связующее дерево ^[3]^{: НД5}
Задача проверки маршрута (также называемая проблемой китайского почтальона ) для смешанных графов (имеющих как направленные, так и неориентированные ребра). Программа разрешима за полиномиальное время, если в графе есть все неориентированные или все направленные ребра. Варианты включают проблему сельского почтальона. ^[3]^{: НД25, НД27}
Проблема с прикрытием клики ^[2]^[3]^{: GT17}
Проблема с щелчком ^[2]^[3]^{: GT19}
Полная раскраска , она же ахроматическое число. ^[3]^{: GT5}
Ранг цикла
Опорное дерево с ограничением по степени ^[3]^{: НД1}
Домашний номер ^[3]^{: GT3}
Доминирующее множество , или число доминирования. ^[3]^{: GT2}

NP-полные частные случаи включают проблему доминирующего множества на ребрах , т. е. проблему доминирующего множества в линейных графах. NP-полные варианты включают задачу связного доминирующего множества и задачу остовного дерева с максимальным листом . ^[3]^{: НД2}

Набор вершин обратной связи ^[2]^[3]^{: GT7}
Набор дуг обратной связи ^[2]^[3]^{: GT8}
Раскраска графа ^[2]^[3]^{: GT4}
гомоморфизма графов Проблема ^[3]^{: GT52}
Разбиение графа на подграфы конкретных типов (треугольники, изоморфные подграфы , гамильтоновы подграфы, леса , совершенные паросочетания ) известны NP-полными. Разбиение на клики — та же задача, что и данного графа раскраска дополнения . Связанная с этим проблема состоит в том, чтобы найти разбиение, оптимальное с точки зрения количества ребер между частями. ^[3]^{: GT11, GT12, GT13, GT14, GT15, GT16, ND14}
Число Гранди ориентированного графа. ^[3]^{: GT56}
гамильтониановое пополнение ^[3]^{: GT34}
Задача о гамильтоновых путях , направленная и неориентированная. ^[2]^[3]^{: GT37, GT38, GT39}
Проблема индуцированного изоморфизма подграфов
Номер пересечения графика ^[3]^{: GT59}
Задача о самом длинном пути ^[3]^{: ND29}
Максимальный двудольный подграф или (особенно с взвешенными ребрами) максимальный разрез . ^[2]^[3]^{: GT25, ND16}
Проблема изоморфизма максимального общего подграфа ^[3]^{: GT49}
Максимальный независимый набор ^[3]^{: GT20}
Максимальный индуцированный путь ^[3]^{: GT23}
Минимальное максимальное независимое множество, также известное как минимальное независимое доминирующее множество. ^[4]

NP-полные частные случаи включают задачу минимального максимального соответствия , ^[3]^{: GT10} что по существу эквивалентно задаче о доминирующем множестве ребер (см. выше).

Метрическая размерность графика ^[3]^{: GT61}
Метрический k-центр
Охватывающее дерево минимальной степени
Минимальный k-образный вырез
Минимальное k-остовное дерево
Незначительное тестирование (проверка того, является ли входной график $G$ содержит входной граф $H$ будучи несовершеннолетним); то же самое относится и к топологическим минорам
Дерево Штейнера , или Минимальное остовное дерево для подмножества вершин графа. ^[2] (Минимальное остовное дерево для всего графа разрешимо за полиномиальное время.)
Максимизация модульности ^[5]
Монохроматический треугольник ^[3]^{: GT6}
Ширина пути , ^[6] или, что то же самое, толщина интервала и число разделений вершин ^[7]
Раскраска рангов
к-китайский почтальон
Кратчайшее связующее дерево общей длины пути ^[3]^: ND3
склона номер два Тестирование ^[8]
Распознавание строковых графов ^[9]
Проблема изоморфизма подграфов ^[3]^{: GT48}
Ширина дерева ^[6]
Проверка того, может ли дерево быть представлено как евклидово минимальное остовное дерево.
Крышка вершины ^[2]^[3]^{: GT1}

Математическое программирование [ править ]

проблема с тремя разделами ^[3]^{: СП15}
Проблема с упаковкой контейнера ^[3]^{: СР1}
Узкий коммивояжёр ^[3]^{: НД24}
Проблема с расположением недееспособного объекта
Задача планирования цеха потока
Обобщенная задача о назначениях
Целочисленное программирование . Вариант, в котором переменные должны быть равны 0 или 1, называется линейным программированием с нулем-единицей, и несколько других вариантов также являются NP-полными. ^[2]^[3]^{: МП1}
Некоторые проблемы, связанные с планированием рабочего места
Задача о рюкзаке , квадратичная задача о рюкзаке и несколько вариантов ^[2]^[3]^:MP9
Некоторые проблемы, связанные с многопроцессорным планированием
Числовое трехмерное сопоставление ^[3]^{: СП16}
График работы открытого цеха
Проблема с разделом ^[2]^[3]^{: СП12}
Задача квадратичного назначения ^[3]^{: ND43}
Квадратичное программирование (в некоторых случаях NP-трудное, P, если выпуклое)
Проблема суммы подмножества ^[3]^{: СП13}
Вариации задачи о коммивояжере . Проблема для графов является NP-полной, если длины ребер считаются целыми числами. Задача для точек на плоскости является NP-полной с дискретизированной евклидовой метрикой и прямолинейной метрикой. Известно, что задача NP-трудна с (недискретизированной) евклидовой метрикой. ^[3]^{: НД22, НД23}
Проблема с маршрутом автомобиля

Формальные языки и обработка строк [ править ]

Ближайшая строка ^[10]
Проблема самой длинной общей подпоследовательности для нескольких последовательностей ^[3]^{: СР10}
Ограниченный вариант задачи о переписке Поста ^[3]^{: СР11}
Кратчайшая общая суперпоследовательность для нескольких последовательностей ^[3]^{: СР8}
Расширение задачи построчной коррекции. ^[11]^[3]^{: СР8}

Игры и головоломки [ править ]

Сумка (Загон) ^[12]
Линкор
Bulls and Cows , продаваемая как Master Mind : определенные проблемы с оптимизацией, но не с самой игрой.
Головоломки с совпадением краев
Филломино ^[13]
( Общий ) FreeCell ^[14]
Гоиси Хирои
Хасивокакеро ^[15]
Хейауэйк ^[16]
( Общее ) Мгновенное безумие ^[3]^{: ГП15}
Какуро (перекрестные суммы) ^[17]
Кингдомино ^[18]
Куромасу (также известный как Куродоко) ^[19]
ЛазерТанк ^[20]
Лемминги (с полиномиальным ограничением по времени) ^[21]
Загораться ^[22]
Пасьянс Маджонг (с просмотром плиток под плитками)
Масю ^[23]
Проблема согласованности Сапера ^[24] (но см. Скотта, Стеге и ван Ройя ^[25])
Нонограммы
Номерная ссылка
Нурикабе ^[26]
( Общая ) Пандемия ^[27]
Одинокий Пег
завершение n-Queens
Оптимальное решение для $N \times N \times N.$ кубика Рубика ^[28]
Та же игра
Шакашака
Slither Link на различных сетках ^[29]^[30]^[31]
( Общее ) Судоку ^[29]^[32]
Татамибари
Тентай Шоу
Проблемы, связанные с Тетрисом ^[33]
Вербальная арифметика

Другое [ править ]

Проблема с размещением причалов ^[34]
Посредничество
Сборка оптимального блока Биткойн . ^[35]
Проблема булевой выполнимости (SAT). ^[2]^[3]^{: ЛО1}Существует множество вариантов, которые также являются NP-полными. Важным вариантом является то, что каждое предложение имеет ровно три литерала (3SAT), поскольку оно используется при доказательстве многих других результатов NP-полноты. ^[3]^{: п. 48}
Проблема выполнимости схемы
Конъюнктивный логический запрос ^[3]^{: СР31}
Циклический заказ ^[36]
Точная проблема с обложкой. Остается NP-полным для 3-х наборов. Разрешимо за полиномиальное время для 2-множеств (это паросочетание ). ^[2]^[3]^{: СП2}
Нахождение глобального минимального решения Хартри-Фока задачи ^[37]
восходящей планарности Проверка ^[8]
Проблема больниц и ординаторов с парами
Род узла ^[38]
Завершение латинского квадрата (проблема определения возможности завершения частично заполненного квадрата)
Максимальная 2-выполнимость ^[3]^{: ЛО5}
максимального объема Подматрица . Проблема выбора наиболее обусловленного подмножества большего объема. $m\times n$ матрица. Этот класс проблем связан с рангом, выявляющим QR-факторизации , и D-оптимальным экспериментальным планом. ^[39]
Минимальные цепочки сложения последовательностей. ^[40] Сложность минимальных цепочек сложения отдельных чисел неизвестна. ^[41]
Модальная логика S5 – Выполнимость
Проблема расстояния сортировки блинов для строк ^[42]
Разрешимость квадратичных многочленов от двух переменных над целыми числами. ^[43] Даны положительные целые числа $\textstyle A,B,C$ , определить существование натуральных чисел $x,y$ такой, что $Ax^{2}+By-C=0$
По той же статье ^[43]существование ограниченных модульных квадратных корней с произвольно составным модулем. Даны положительные целые числа $\textstyle A,B,C\geq 0$ , определить существование целого числа $x\in [0,C]$ такой, что $x^{2}\equiv A{\bmod {B}}$ . Задача остается NP-полной, даже если факторизация простая $B$ предоставлен.
Сериализуемость истории базы данных ^[3]^{: СР33}
Покрытие множества (также называемое проблемой минимального покрытия ). За счет транспонирования матрицы инцидентности это эквивалентно проблеме множества попаданий. ^[2]^[3]^{: СП5, СП8}
Упаковка комплекта ^[2]^[3]^{: СП3}
Установить задачу разделения ^[3]^:SP4
Планирование для минимизации взвешенного времени завершения
Сортировка блоков ^[44] (Сортировка по ходам блоков)
Разреженное приближение
Варианты задачи о дереве Штейнера . В частности, с дискретизированной евклидовой метрикой, прямолинейной метрикой. Известно, что задача NP-трудна с (недискретизированной) евклидовой метрикой. ^[3]^{: ND13}
Трехмерная модель Изинга ^[45]

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

Примечания [ править ]

^ Григорьев и Бодлаендер (2007) .
^ Перейти обратно: ^а ^б ^с ^д ^Это ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^О ^п ^д Карп (1972)
^ Перейти обратно: ^а ^б ^с ^д ^Это ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^О ^п ^д ^р ^с ^т ^в ^v ^В ^Икс ^и ^С ^аа ^аб ^и ^{объявление} ^но ^из ^в ^ах ^есть ^также ^и ^аль ^{являюсь} ^а ^к ^ап ^ак ^С ^как ^в ^В ^из ^хорошо ^топор ^{является} ^тот ^нет ^бб ^{До нашей эры} ^др. ^быть Гэри и Джонсон (1979)
^ Минимальный независимый доминирующий набор
^ Брандес, Ульрик ; Деллинг, Дэниел; Гертлер, Марко; Гёрке, Роберт; Хофер, Мартин; Николоски, Зоран; Вагнер, Доротея (2006), Максимизировать модульность сложно , arXiv : физика/0608255 , Bibcode : 2006физика...8255B
^ Перейти обратно: ^а ^б Арнборг, Корней и Проскуровски (1987)
^ Кашивабара и Фудзисава (1979) ; и др. ( Оцуки ) 1979
^ Перейти обратно: ^а ^б Гарг, Ашим; Тамассия, Роберто (1995). «О вычислительной сложности проверки восходящей и прямолинейной планарности». Конспекты лекций по информатике . Том. 894/1995. стр. 286–297. дои : 10.1007/3-540-58950-3_384 . ISBN 978-3-540-58950-1 .
^ Шефер, Маркус; Седжвик, Эрик; Штефанкович, Даниэль (сентябрь 2003 г.). «Распознавание строковых графов в NP» . Журнал компьютерных и системных наук . 67 (2): 365–380. дои : 10.1016/S0022-0000(03)00045-X .
^ Ланкто, Дж. Кевин; Ли, Мин; Ма, Бин; Ван, Шаоцзю; Чжан, Лусинь (2003), «Выявление проблем выбора строк», Information and Computation , 185 (1): 41–55, doi : 10.1016/S0890-5401(03)00057-9 , MR 1994748
^ Вагнер, Роберт А. (май 1975 г.). «О сложности расширенной задачи построчной коррекции» . Материалы седьмого ежегодного симпозиума ACM по теории вычислений - STOC '75 . стр. 218–223. дои : 10.1145/800116.803771 . ISBN 9781450374194 . S2CID 18705107 .
^ Фридман, Эрих. «Загадки коррала являются NP-полными» (PDF) . Проверено 17 августа 2021 г.
^ Ято, Такауки (2003). Сложность и полнота поиска другого решения и его применение к головоломкам . CiteSeerX 10.1.1.103.8380 .
^ Мальте Хелмерт, Результаты сложности для стандартных контрольных областей при планировании, Искусственный интеллект 143 (2): 219-262, 2003.
^ «ХАСИВОКАКЕРО NP-полный» .
^ Хольцер и Руепп (2007)
^ Такахиро, Сета (5 февраля 2002 г.). «Сложности головоломок, перекрестная сумма и другие задачи их решения (ASP)» (PDF) . Проверено 18 ноября 2018 г.
^ Нгуен, Вьет-Ха; Перро, Кевин; Валлет, Матье (24 июня 2020 г.). «NP-полнота игры KingdominoTM» . Теоретическая информатика . 822 : 23–35. дои : 10.1016/j.tcs.2020.04.007 . ISSN 0304-3975 . S2CID 218552723 .
^ Кёлькер, Йонас (2012). «Куродоко NP-полна» (PDF) . Журнал обработки информации . 20 (3): 694–706. дои : 10.2197/ipsjjip.20.694 . S2CID 46486962 . Архивировано из оригинала (PDF) 12 февраля 2020 года.
^ Александерссон, Пер; Рестад, Петтер (2020). «LaserTank является NP-полным». Математические аспекты компьютерных и информационных наук . Конспекты лекций по информатике. Том. 11989. Международное издательство Springer. стр. 333–338. arXiv : 1908.05966 . дои : 10.1007/978-3-030-43120-4_26 . ISBN 978-3-030-43119-8 . S2CID 201058355 .
^ Кормод, Грэм (2004). Сложность игры с леммингами, или О нет, еще доказательства NP-полноты (PDF) .
^ Light Up является NP-полным.
^ Фридман, Эрих (27 марта 2012 г.). «Жемчужные головоломки NP-полны» . Архивировано из оригинала 4 февраля 2012 года.
^ Кэй (2000)
^ Аллан Скотт, Ульрика Стеге, Ирис ван Рой, Сапер, возможно, не является NP-полным, но, тем не менее, сложен, The Mathematical Intelligencer 33 :4 (2011), стр. 5–17.
^ Хольцер, Маркус; Кляйн, Андреас; Кутриб, Мартин; Рупп, Оливер (2011). «Вычислительная сложность НУРИКАБЕ». Фундамента информатика . 110 (1–4): 159–174. дои : 10.3233/FI-2011-534 .
^ Накаи, Кеничиро; Такенага, Ясухико (2012). «НП-Завершенность пандемии» . Журнал обработки информации . 20 (3): 723–726. дои : 10.2197/ipsjjip.20.723 . ISSN 1882-6652 .
^ Демейн, Эрик; Эйзенштат, Сара; Рудой, Михаил (2018). Оптимальное решение кубика Рубика является NP-полным . 35-й симпозиум по теоретическим аспектам информатики (STACS 2018). doi : 10.4230/LIPIcs.STACS.2018.24 .
^ Перейти обратно: ^а ^б Сато, Такаюки; Сета, Такахиро (1987). Сложность и полнота поиска другого решения и его применение к головоломкам (PDF) . Международный симпозиум по алгоритмам (SIGAL 1987).
^ Нукуи; Уэдзима (март 2007 г.). «ASP-полнота головоломки со скользящими звеньями на нескольких сетках» . Примечания к подписи Ipsj . 2007 (23): 129–136.
^ Кёлькер, Йонас (2012). «Выбранные варианты скользящих звеньев являются NP-полными» . Журнал обработки информации . 20 (3): 709–712. дои : 10.2197/ipsjjip.20.709 .
^ ОБЗОР NP-ПОЛНЫХ ЗАГАДОК, Раздел 23; Грэм Кендалл, Эндрю Паркс, Кристиан Сперер; Март 2008 г. (icga2008.pdf)
^ Демейн, Эрик Д.; Хоэнбергер, Сьюзен; Либен-Ноуэлл, Дэвид (25–28 июля 2003 г.). Тетрис сложно даже приблизить (PDF) . Материалы 9-й Международной конференции по вычислительной технике и комбинаторике (COCOON 2003) . Биг Скай, Монтана.
^ Лим, Эндрю (1998), «Проблема планирования причала», Operations Research Letters , 22 (2–3): 105–110, doi : 10.1016/S0167-6377(98)00010-8 , MR 1653377
^ Дж. Бонно, «Майнинг биткойнов NP-сложный»
^ Галил, Цви; Мегиддо, Нимрод (октябрь 1977 г.). «Циклический порядок является NP-полным» . Теоретическая информатика . 5 (2): 179–182. дои : 10.1016/0304-3975(77)90005-6 .
^ Уитфилд, Джеймс Дэниел; С любовью, Питер Джон; Аспуру-Гузик, Алан (2013). «Вычислительная сложность в электронных структурах» . Физ. хим. хим. Физ . 15 (2): 397–411. arXiv : 1208.3334 . Бибкод : 2013PCCP...15..397W . дои : 10.1039/C2CP42695A . ПМИД 23172634 . S2CID 12351374 .
^ Агол, Ян ; Хасс, Джоэл ; Терстон, Уильям (19 мая 2002 г.). «Род узлов 3-многообразия NP-полный» . Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . СТОК '02. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 761–766. arXiv : math/0205057 . дои : 10.1145/509907.510016 . ISBN 978-1-58113-495-7 . S2CID 10401375 .
^ Чиврил, Али; Магдон-Исмаил, Малик (2009), «О выборе подматрицы максимального объема матрицы и связанных с этим проблемах» (PDF) , Theoretical Computer Science , 410 (47–49): 4801–4811, doi : 10.1016/j. tcs.2009.06.018 , MR 2583677 , заархивировано из оригинала (PDF) 3 февраля 2015 г.
^ Питер Дауни, Бентон Леонг и Рави Сетхи. «Вычисление последовательностей с помощью цепочек сложения» SIAM J. Comput., 10 (3), 638–646, 1981.
^ DJ Бернштейн, «Алгоритм возведения в степень Пиппингера» (проект)
^ Херкенс, К.; Иерсель, LV; Кейспер, Дж.; Келк, С.; Стуги, Л.; Тромп, Дж. (2007). «Реверсирование префиксов в двоичных и троичных строках». СИАМ Дж. Дискретная математика . 21 (3): 592–611. arXiv : math/0602456 . дои : 10.1137/060664252 .
^ Перейти обратно: ^а ^б Мандерс, Кеннет; Адлеман, Леонард (1976). «NP-полные задачи решения для квадратных многочленов» . Материалы восьмого ежегодного симпозиума ACM по теории вычислений - STOC '76 . стр. 23–29. дои : 10.1145/800113.803627 . ISBN 9781450374149 . S2CID 18885088 .
^ Бейн, WW; Лармор, LL; Латифи, С.; Садборо, Айдахо (1 января 2002 г.). «Сортировка блоков сложна». Труды Международного симпозиума по параллельным архитектурам, алгоритмам и сетям. Я-СПАН'02 . стр. 307–312. дои : 10.1109/ИСПАН.2002.1004305 . ISBN 978-0-7695-1579-3 . S2CID 32222403 .
^ Барри Артур Ципра , «Модель Изинга NP-полна», SIAM News, Том 33, № 6.

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

Общий

Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 . . Эта книга представляет собой классику, в которой развивается теория, а затем каталогизируется множество NP-полных проблем.
Кук, С.А. (1971). «Сложность процедур доказательства теорем». Труды Третьего ежегодного симпозиума ACM по теории вычислений, ACM, Нью-Йорк . стр. 151–158. дои : 10.1145/800157.805047 .
Карп, Ричард М. (1972). «Сводимость среди комбинаторных задач». В Миллере, Раймонде Э.; Тэтчер, Джеймс В. (ред.). Сложность компьютерных вычислений . Пленум. стр. 85–103.
Данн, PE «Аннотированный список избранных NP-полных задач» . COMP202, факультет компьютерных наук, Ливерпульский университет . Проверено 21 июня 2008 г.
Крещенци, П.; Канн, В.; Халлдорссон, М.; Карпински, М .; Вегингер, Г. «Сборник задач оптимизации NP» . КТН НАДА, Стокгольм . Проверено 21 июня 2008 г.
Дальке, К. «NP-полные задачи» . Справочный проект по математике . Проверено 21 июня 2008 г.

Конкретные проблемы

Фридман, Э. (2002). «Жемчужные головоломки NP-полны» . Стетсонский университет, ДеЛанд, Флорида. Архивировано из оригинала 4 сентября 2006 года . Проверено 21 июня 2008 г.
Григорьев А; Бодлендер, HL (2007). «Алгоритмы для встраиваемых графов с небольшим количеством пересечений на ребро». Алгоритмика . 49 (1): 1–11. CiteSeerX 10.1.1.61.3576 . дои : 10.1007/s00453-007-0010-x . МР 2344391 . S2CID 8174422 .
Хартунг, С; Нихтерляйн, А (2012). «NP-твердость и управляемость с фиксированными параметрами реализации последовательностей степеней с помощью направленных ациклических графов». Как мир считает . Конспекты лекций по информатике. Том. 7318. Шпрингер, Берлин, Гейдельберг. стр. 283–292. CiteSeerX 10.1.1.377.2077 . дои : 10.1007/978-3-642-30870-3_29 . ISBN 978-3-642-30869-7 . S2CID 6112925 .
Хольцер, Маркус; Рупп, Оливер (2007). «Проблемы дизайна интерьера – анализ сложности игры Heyawake» (PDF) . Материалы 4-й Международной конференции по развлечениям с алгоритмами, LNCS 4475 . Шпрингер, Берлин/Гейдельберг. стр. 198–212. дои : 10.1007/978-3-540-72914-3_18 . ISBN 978-3-540-72913-6 .
Кэй, Ричард (2000). «Сапер NP-полный». Математический интеллект . 22 (2): 9–15. дои : 10.1007/BF03025367 . S2CID 122435790 . Дополнительную информацию можно найти в Интернете на страницах Сапера Ричарда Кея .
Кашивабара, Т.; Фудзисава, Т. (1979). «NP-полнота задачи поиска графа интервалов с минимальным числом клик, содержащего данный граф в качестве подграфа». Слушания . Международный симпозиум по схемам и системам . стр. 657–660.
Оцуки, Тацуо; Мори, Хаджиму; Кух, Эрнест С.; Касивабара, Тошинобу; Фудзисава, Тосио (1979). «Одномерное назначение логических вентилей и интервальные графики». Транзакции IEEE в схемах и системах . 26 (9): 675–684. дои : 10.1109/TCS.1979.1084695 .
Ленгауэр, Томас (1981). «Черно-белые камешки и разделение графов». Акта Информатика . 16 (4): 465–475. дои : 10.1007/BF00264496 . S2CID 19415148 .
Арнборг, Стефан; Корнейл, Дерек Г .; Проскуровский, Анджей (1987). «Сложность поиска вложений в k -дереве». SIAM Journal по алгебраическим и дискретным методам . 8 (2): 277–284. дои : 10.1137/0608024 .
Кормод, Грэм (2004). «Трудность игры с леммингами, или О нет, еще доказательства NP-полноты». Материалы Третьей международной конференции по развлечениям с алгоритмами (FUN 2004) . стр. 65–76.

Внешние ссылки [ править ]

[FOOTNOTEGrigorievBodlaender2007-1] Григорьев и Бодлаендер (2007) .

[karp-2] Перейти обратно: ^а ^б ^с ^д ^Это ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^О ^п ^д Карп (1972)

[gj1979-3] Перейти обратно: ^а ^б ^с ^д ^Это ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^О ^п ^д ^р ^с ^т ^в ^v ^В ^Икс ^и ^С ^аа ^аб ^и ^{объявление} ^но ^из ^в ^ах ^есть ^также ^и ^аль ^{являюсь} ^а ^к ^ап ^ак ^С ^как ^в ^В ^из ^хорошо ^топор ^{является} ^тот ^нет ^бб ^{До нашей эры} ^др. ^быть Гэри и Джонсон (1979)

[4] Минимальный независимый доминирующий набор

[5] Брандес, Ульрик ; Деллинг, Дэниел; Гертлер, Марко; Гёрке, Роберт; Хофер, Мартин; Николоски, Зоран; Вагнер, Доротея (2006), Максимизировать модульность сложно , arXiv : физика/0608255 , Bibcode : 2006физика...8255B

[acp1987-6] Перейти обратно: ^а ^б Арнборг, Корней и Проскуровски (1987)

[7] Кашивабара и Фудзисава (1979) ; и др. ( Оцуки ) 1979

[Comp2Planar-8] Перейти обратно: ^а ^б Гарг, Ашим; Тамассия, Роберто (1995). «О вычислительной сложности проверки восходящей и прямолинейной планарности». Конспекты лекций по информатике . Том. 894/1995. стр. 286–297. дои : 10.1007/3-540-58950-3_384 . ISBN 978-3-540-58950-1 .

[9] Шефер, Маркус; Седжвик, Эрик; Штефанкович, Даниэль (сентябрь 2003 г.). «Распознавание строковых графов в NP» . Журнал компьютерных и системных наук . 67 (2): 365–380. дои : 10.1016/S0022-0000(03)00045-X .

[10] Ланкто, Дж. Кевин; Ли, Мин; Ма, Бин; Ван, Шаоцзю; Чжан, Лусинь (2003), «Выявление проблем выбора строк», Information and Computation , 185 (1): 41–55, doi : 10.1016/S0890-5401(03)00057-9 , MR 1994748

[11] Вагнер, Роберт А. (май 1975 г.). «О сложности расширенной задачи построчной коррекции» . Материалы седьмого ежегодного симпозиума ACM по теории вычислений - STOC '75 . стр. 218–223. дои : 10.1145/800116.803771 . ISBN 9781450374194 . S2CID 18705107 .

[12] Фридман, Эрих. «Загадки коррала являются NP-полными» (PDF) . Проверено 17 августа 2021 г.

[13] Ято, Такауки (2003). Сложность и полнота поиска другого решения и его применение к головоломкам . CiteSeerX 10.1.1.103.8380 .

[14] Мальте Хелмерт, Результаты сложности для стандартных контрольных областей при планировании, Искусственный интеллект 143 (2): 219-262, 2003.

[15] «ХАСИВОКАКЕРО NP-полный» .

[Holzer-Ruepp07-16] Хольцер и Руепп (2007)

[17] Такахиро, Сета (5 февраля 2002 г.). «Сложности головоломок, перекрестная сумма и другие задачи их решения (ASP)» (PDF) . Проверено 18 ноября 2018 г.

[18] Нгуен, Вьет-Ха; Перро, Кевин; Валлет, Матье (24 июня 2020 г.). «NP-полнота игры KingdominoTM» . Теоретическая информатика . 822 : 23–35. дои : 10.1016/j.tcs.2020.04.007 . ISSN 0304-3975 . S2CID 218552723 .

[Kölker12b-19] Кёлькер, Йонас (2012). «Куродоко NP-полна» (PDF) . Журнал обработки информации . 20 (3): 694–706. дои : 10.2197/ipsjjip.20.694 . S2CID 46486962 . Архивировано из оригинала (PDF) 12 февраля 2020 года.

[20] Александерссон, Пер; Рестад, Петтер (2020). «LaserTank является NP-полным». Математические аспекты компьютерных и информационных наук . Конспекты лекций по информатике. Том. 11989. Международное издательство Springer. стр. 333–338. arXiv : 1908.05966 . дои : 10.1007/978-3-030-43120-4_26 . ISBN 978-3-030-43119-8 . S2CID 201058355 .

[Cormode04-21] Кормод, Грэм (2004). Сложность игры с леммингами, или О нет, еще доказательства NP-полноты (PDF) .

[22] Light Up является NP-полным.

[Friedman-23] Фридман, Эрих (27 марта 2012 г.). «Жемчужные головоломки NP-полны» . Архивировано из оригинала 4 февраля 2012 года.

[24] Кэй (2000)

[25] Аллан Скотт, Ульрика Стеге, Ирис ван Рой, Сапер, возможно, не является NP-полным, но, тем не менее, сложен, The Mathematical Intelligencer 33 :4 (2011), стр. 5–17.

[26] Хольцер, Маркус; Кляйн, Андреас; Кутриб, Мартин; Рупп, Оливер (2011). «Вычислительная сложность НУРИКАБЕ». Фундамента информатика . 110 (1–4): 159–174. дои : 10.3233/FI-2011-534 .

[27] Накаи, Кеничиро; Такенага, Ясухико (2012). «НП-Завершенность пандемии» . Журнал обработки информации . 20 (3): 723–726. дои : 10.2197/ipsjjip.20.723 . ISSN 1882-6652 .

[28] Демейн, Эрик; Эйзенштат, Сара; Рудой, Михаил (2018). Оптимальное решение кубика Рубика является NP-полным . 35-й симпозиум по теоретическим аспектам информатики (STACS 2018). doi : 10.4230/LIPIcs.STACS.2018.24 .

[sigal87-29] Перейти обратно: ^а ^б Сато, Такаюки; Сета, Такахиро (1987). Сложность и полнота поиска другого решения и его применение к головоломкам (PDF) . Международный симпозиум по алгоритмам (SIGAL 1987).

[NU07-30] Нукуи; Уэдзима (март 2007 г.). «ASP-полнота головоломки со скользящими звеньями на нескольких сетках» . Примечания к подписи Ipsj . 2007 (23): 129–136.

[Kölker12c-31] Кёлькер, Йонас (2012). «Выбранные варианты скользящих звеньев являются NP-полными» . Журнал обработки информации . 20 (3): 709–712. дои : 10.2197/ipsjjip.20.709 .

[32] ОБЗОР NP-ПОЛНЫХ ЗАГАДОК, Раздел 23; Грэм Кендалл, Эндрю Паркс, Кристиан Сперер; Март 2008 г. (icga2008.pdf)

[33] Демейн, Эрик Д.; Хоэнбергер, Сьюзен; Либен-Ноуэлл, Дэвид (25–28 июля 2003 г.). Тетрис сложно даже приблизить (PDF) . Материалы 9-й Международной конференции по вычислительной технике и комбинаторике (COCOON 2003) . Биг Скай, Монтана.

[34] Лим, Эндрю (1998), «Проблема планирования причала», Operations Research Letters , 22 (2–3): 105–110, doi : 10.1016/S0167-6377(98)00010-8 , MR 1653377

[35] Дж. Бонно, «Майнинг биткойнов NP-сложный»

[36] Галил, Цви; Мегиддо, Нимрод (октябрь 1977 г.). «Циклический порядок является NP-полным» . Теоретическая информатика . 5 (2): 179–182. дои : 10.1016/0304-3975(77)90005-6 .

[37] Уитфилд, Джеймс Дэниел; С любовью, Питер Джон; Аспуру-Гузик, Алан (2013). «Вычислительная сложность в электронных структурах» . Физ. хим. хим. Физ . 15 (2): 397–411. arXiv : 1208.3334 . Бибкод : 2013PCCP...15..397W . дои : 10.1039/C2CP42695A . ПМИД 23172634 . S2CID 12351374 .

[38] Агол, Ян ; Хасс, Джоэл ; Терстон, Уильям (19 мая 2002 г.). «Род узлов 3-многообразия NP-полный» . Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . СТОК '02. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 761–766. arXiv : math/0205057 . дои : 10.1145/509907.510016 . ISBN 978-1-58113-495-7 . S2CID 10401375 .

[39] Чиврил, Али; Магдон-Исмаил, Малик (2009), «О выборе подматрицы максимального объема матрицы и связанных с этим проблемах» (PDF) , Theoretical Computer Science , 410 (47–49): 4801–4811, doi : 10.1016/j. tcs.2009.06.018 , MR 2583677 , заархивировано из оригинала (PDF) 3 февраля 2015 г.

[40] Питер Дауни, Бентон Леонг и Рави Сетхи. «Вычисление последовательностей с помощью цепочек сложения» SIAM J. Comput., 10 (3), 638–646, 1981.

[41] DJ Бернштейн, «Алгоритм возведения в степень Пиппингера» (проект)

[42] Херкенс, К.; Иерсель, LV; Кейспер, Дж.; Келк, С.; Стуги, Л.; Тромп, Дж. (2007). «Реверсирование префиксов в двоичных и троичных строках». СИАМ Дж. Дискретная математика . 21 (3): 592–611. arXiv : math/0602456 . дои : 10.1137/060664252 .

[NP-complete_decision_problems_for_Quadratic_Polynomials-43] Перейти обратно: ^а ^б Мандерс, Кеннет; Адлеман, Леонард (1976). «NP-полные задачи решения для квадратных многочленов» . Материалы восьмого ежегодного симпозиума ACM по теории вычислений - STOC '76 . стр. 23–29. дои : 10.1145/800113.803627 . ISBN 9781450374149 . S2CID 18885088 .

[44] Бейн, WW; Лармор, LL; Латифи, С.; Садборо, Айдахо (1 января 2002 г.). «Сортировка блоков сложна». Труды Международного симпозиума по параллельным архитектурам, алгоритмам и сетям. Я-СПАН'02 . стр. 307–312. дои : 10.1109/ИСПАН.2002.1004305 . ISBN 978-0-7695-1579-3 . S2CID 32222403 .

[45] Барри Артур Ципра , «Модель Изинга NP-полна», SIAM News, Том 33, № 6.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]