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

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

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

Графы и гиперграфы

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

• 1-планарность^[1]
• 3-мерное соответствие^[2][3]
• Двудольное измерение^[4]
• Емкостное минимальное остовное дерево^[5]
• Проблема проверки маршрута (также называемый Проблема китайского почтальона) за смешанные графики (с направленными и ненаправленными краями). Программа разрешима за полиномиальное время, если в графе есть все неориентированные или все ориентированные ребра. Варианты включают задачу сельского почтальона.^[6]
• Проблема клики^[2][7]
• Полная окраска, также известное как ахроматическое число^[8]
• Датический номер^[9]
• Доминирующий набор, он же номер господства^[10]

NP-полные частные случаи включают набор с доминирующим краем проблема доминирующего множества в линейных графах. NP-полные варианты включают связное доминирующее множество проблема и максимальное остовное дерево проблема.^[11]

• Проблема с пропускной способностью^[12]
• Проблема покрытия клики^[2][13]
• Раскраска рангов также известный как ранг цикла
• Остовное дерево с ограничениями по степени^[14]
• Точное покрытие проблема. Остается NP-полная для 3-х комплектов. Разрешается за полиномиальное время для 2-множеств (это соответствие ).^[2][15]
• Набор вершин обратной связи^[2][16]
• Набор дуг обратной связи^[2][17]
• Гомоморфизм графов проблема^[18]
• Раскраска графика^[2][19]
• Раздел графа в подграфы определенных типов (треугольники, изоморфный подграфы, Гамильтониан подграфы, леса, идеальное соответствие ) известны NP-полными. Разделение на клики та же проблема, что и раскраска то дополнять данного графа. Связанная с этим проблема - найти раздел, который является оптимальным по количеству ребер между частями.^[20]
• Гамильтоново пополнение^[21]
• Гамильтонова проблема пути, направленный и ненаправленный.^[2][22]
• Проблема самого длинного пути^[23]
• Максимальный двудольный подграф или (особенно со взвешенными ребрами) максимальный разрез.^[2][24]
• Максимальный независимый набор^[25]
• Максимум Индуцированный путь^[26]
• Номер пересечения графика^[27]
• Метрический параметр графа^[28]
• Минимальный k-разрез
• Дерево Штейнера, или же Минимальное остовное дерево для подмножества вершин графа.^[2] (Минимальное остовное дерево для всего графа разрешимо за полиномиальное время.)
• Максимизация модульности^[29]
• Ширина пути^[30]
• Установить обложку (также называемый минимальное покрытие проблема) Это эквивалентно, транспонируя матрицу инцидентности, задаче попадания множества.^[2][31]
• Установить разделение проблема^[32]
• Остовное дерево кратчайшей общей длины пути^[33]
• Номер откоса два испытания^[34]
• Ширина дерева^[30]
• Крышка Vertex^[2][35]

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

• Проблема с 3 разделами^[36]
• Проблема с упаковкой бункера^[37]
• Задача о рюкзаке, квадратичная задача о рюкзаке, и несколько вариантов^[2][38]
• Вариации на тему Проблема коммивояжера. Проблема для графов NP-полная, если длины ребер предполагаются целыми числами. Задача для точек на плоскости является NP-полной с дискретной евклидовой метрикой и прямолинейной метрикой. Известно, что проблема NP-сложна с (недискретизированной) евклидовой метрикой.^[39]
• Коммивояжер^[40]
• Целочисленное программирование. Вариант, в котором переменные должны быть равны 0 или 1, называется линейным программированием нуля или единицы, и несколько других вариантов также являются NP-полными.^[2][41]
• Латинские квадраты (Проблема определения, можно ли заполнить частично заполненный квадрат, чтобы сформировать его)
• Численное 3-мерное сопоставление^[42]
• Проблема с разделом^[2][43]
• Квадратичная задача о назначении^[44]
• Решение квадратичных многочленов с двумя переменными над целыми числами.^[45] Учитывая положительные целые числа ${\displaystyle \textstyle A,B,C\geq 0}$, найти положительные целые числа ${\displaystyle x,y}$ такой, что ${\displaystyle Ax^{2}+By-C=0}$
• Квадратичное программирование (NP-жесткий в некоторых случаях, P, если выпуклый)
• Проблема суммы подмножества^[46]

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

• Ближайшая строка^[47]
• Самая длинная общая проблема подпоследовательности по нескольким последовательностям^[48]
• Ограниченный вариант Проблема с почтовой перепиской^[49]
• Кратчайшая общая суперпоследовательность^[50]
• Проблема исправления строки в строку^[51]

Игры и головоломки

• Линкор
• Быки и коровы, продается как Главный разум: определенные проблемы с оптимизацией, но не сама игра.
• Вечность II
• (Обобщенный ) Свободная ячейка^[52]
• Филломино^[53]
• Хашивокакеро^[54]
• Heyawake^[55]
• (Обобщенный ) Мгновенное безумие^[56]
• Какуро (кросс-суммы)
• Kingdomino^[57]
• Куромасу (также известный как Куродоко)^[58]
• LaserTank ^[59]
• Лемминги (с полиномиальным ограничением времени)^[60]
• Загораться^[61]
• Масю^[62]
• Проблема согласованности саперов^[63] (но см. Скотт, Стеге и ван Рой^[64])
• Нимбер (или число Гранди) ориентированного графа.^[65]
• Номер ссылка
• Нонограммы
• Нурикабе
• (Обобщенный ) Пандемия^[66]
• Оптимальное решение для N×N×N Кубик Рубика^[67]
• SameGame
• (Обобщенный ) Набор^[68]
• Скользящая ссылка на различных сетках^[69][70][71]
• (Обобщенный ) Судоку^[69][72]
• Проблемы, связанные с Тетрис^[73]
• Вербальная арифметика

Другой

• Проблема размещения причалов^[74]
• Близость
• Сборка оптимального Биткойн блокировать.^[75]
• Проблема логической выполнимости (СИДЕЛ).^[2][76] Есть много вариантов, которые также являются NP-полными. Важным вариантом является то, что каждое предложение имеет ровно три литерала (3SAT), поскольку оно используется при доказательстве многих других результатов NP-полноты.^[77]
• Конъюнктивный логический запрос^[78]
• Циклический заказ
• Проблема выполнимости схемы
• Проблема с расположением неработающего объекта
• Проблема планирования производственного процесса
• Обобщенная проблема присваивания
• Восходящая планарность тестирование^[34]
• Проблема больниц и жителей с парами
• Некоторые проблемы, связанные с Планирование работы магазина
• Монохромный треугольник^[79]
• Минимальный максимальный независимый набор a.k.a. минимальный независимый доминирующий набор^[80]

NP-полные частные случаи включают минимальное максимальное соответствие проблема,^[81] что по существу равно набор с доминирующим краем проблема (см. выше).

• Проблема изоморфизма максимального общего подграфа^[82]
• Остовное дерево минимальной степени
• Минимальное k-остовное дерево
• Метрический k-центр
• Максимальная 2-выполнимость^[83]
• Модальная логика S5-Выполнимость
• Некоторые проблемы, связанные с Многопроцессорное планирование
• Максимальная громкость подматрица - Проблема выбора наилучшего условного подмножества большей матрицы m x n. Этот класс проблем связан с выявлением ранга. QR-факторизации и D. Оптимальный экспериментальный план.^[84]
• Минимальный цепочки сложения для последовательностей.^[85] Сложность минимальных цепочек сложения отдельных чисел неизвестна.^[86]
• Нелинейные одномерные многочлены над GF [2^п], n - длина входа. Действительно, над любой GF [q^п].
• Планирование открытых магазинов
• Ширина пути,^[30] или, что то же самое, толщина интервала, и число разделения вершин^[87]
• Сортировка блинов проблема расстояния для струн^[88]
• к-китайский почтальон
• Проблема изоморфизма подграфов^[89]
• Вариации Проблема дерева Штейнера. В частности, с дискретизированной евклидовой метрикой, прямолинейной метрикой. Известно, что проблема NP-трудна с (недискретизированной) евклидовой метрикой.^[90]
• Комплект упаковки^[2][91]
• Сериализуемость историй базы данных^[92]
• Планирование для минимизации взвешенного времени завершения
• Разреженное приближение
• Блочная сортировка^[93] (Сортировка по ходам блоков)
• Второго порядка реализация
• Ширина дерева^[30]
• Проверка того, есть ли дерево может быть представлен как Евклидово минимальное остовное дерево
• Трехмерный Модель Изинга^[94]
• Проблема с маршрутизацией автомобиля

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

• Экзистенциальная теория реальности # Полные задачи
• 21 NP-полная задача Карпа
• Список проблем PSPACE-complete
• Редукция (сложность)

Примечания

1. Григорьев и Бодлендер (2007).
2. Карп (1972)
3. Гэри и Джонсон (1979): SP1
4. Гэри и Джонсон (1979): GT18
5. Гэри и Джонсон (1979): ND5
6. Гэри и Джонсон (1979): ND25, ND27
7. Гэри и Джонсон (1979): GT19
8. Гэри и Джонсон (1979): GT5
9. Гэри и Джонсон (1979): GT3
10. Гэри и Джонсон (1979): GT2
11. Гэри и Джонсон (1979): ND2
12. Гэри и Джонсон (1979): GT40
13. Гэри и Джонсон (1979): GT17
14. Гэри и Джонсон (1979): ND1
15. Гэри и Джонсон (1979): SP2
16. Гэри и Джонсон (1979): GT7
17. Гэри и Джонсон (1979): GT8
18. Гэри и Джонсон (1979): GT52
19. Гэри и Джонсон (1979): GT4
20. Гэри и Джонсон (1979): GT11, GT12, GT13, GT14, GT15, GT16, ND14
21. Гэри и Джонсон (1979): GT34
22. Гэри и Джонсон (1979): GT37, GT38, GT39
23. Гэри и Джонсон (1979): ND29
24. Гэри и Джонсон (1979): GT25, ND16
25. Гэри и Джонсон (1979): GT20
26. Гэри и Джонсон (1979): GT23
27. Гэри и Джонсон (1979): GT59
28. Гэри и Джонсон (1979): GT61
29. Брандес, Ульрик; Деллинг, Дэниел; Гертлер, Марко; Гёрке, Роберт; Хофер, Мартин; Николоски, Зоран; Вагнер, Доротея (2006), Максимизировать модульность сложно, arXiv:физика / 0608255, Bibcode:2006физика ... 8255B
30. Арнборг, Корнейл и Проскуровски (1987)
31. Гэри и Джонсон (1979): SP5, SP8
32. Гэри и Джонсон (1979): SP4
33. Гэри и Джонсон (1979): ND3
34. Гарг, Ашим; Тамассия, Роберто (1995). «О вычислительной сложности тестирования восходящей и прямолинейной планарности». Конспект лекций по информатике. 894/1995. С. 286–297. Дои:10.1007/3-540-58950-3_384. ISBN  978-3-540-58950-1.
35. Гэри и Джонсон (1979): GT1
36. Гэри и Джонсон (1979): SP15
37. Гэри и Джонсон (1979): SR1
38. Гэри и Джонсон (1979): MP9
39. Гэри и Джонсон (1979): ND22, ND23
40. Гэри и Джонсон (1979): ND24
41. Гэри и Джонсон (1979): MP1
42. Гэри и Джонсон (1979): SP16
43. Гэри и Джонсон (1979): SP12
44. Гэри и Джонсон (1979): ND43
45. NP-полные задачи решения квадратичных многочленов
46. Гэри и Джонсон (1979): SP13
47. Ланкто, Дж. Кевин; Ли, Мин; Ма, Бин; Ван, Шаоцзю; Чжан, Луксинь (2003), «Выявление проблем с выбором строки», Информация и вычисления, 185 (1): 41–55, Дои:10.1016 / S0890-5401 (03) 00057-9, МИСТЕР  1994748
48. Гэри и Джонсон (1979): SR10
49. Гэри и Джонсон (1979): SR11
50. Гэри и Джонсон (1979): SR8
51. Гэри и Джонсон (1979): SR20
52. Мальте Хельмерт, Результаты сложности для стандартных тестовых областей в планировании, Искусственный интеллект 143 (2): 219-262, 2003.
53. Ято, Такауки (2003). Сложность и полнота поиска другого решения и его применение к головоломкам. CiteSeerX  10.1.1.103.8380.
54. "HASHIWOKAKERO является NP-Complete".
55. Хольцер и Рупп (2007)
56. Гэри и Джонсон (1979): GP15
57. Нгуен, Вьет-Ха; Перро, Кевин; Валле, Матье (24 июня 2020 г.). «NP-полнота игры KingdominoTM». Теоретическая информатика. 822: 23–35. Дои:10.1016 / j.tcs.2020.04.007. ISSN  0304-3975.
58. Кёлькер, Йонас (2012). «Куродоко НП-завершена» (PDF). Журнал обработки информации. 20 (3): 694–706. Дои:10.2197 / ipsjjip.20.694. S2CID  46486962.
59. Александерссон, Пер; Рестад, Петтер (2020). «LaserTank - это NP-Complete». Математические аспекты компьютерных и информационных наук. Конспект лекций по информатике. Издательство Springer International. 11989: 333–338. arXiv:1908.05966. Дои:10.1007/978-3-030-43120-4_26. ISBN  978-3-030-43119-8. S2CID  201058355.
60. Кормод, Грэм (2004). Жесткость игры леммингов, или О нет, еще доказательства NP-полноты (PDF).
61. Light Up - это NP-Complete
62. Фридман, Эрих (27 марта 2012 г.). «Жемчужные пазлы NP-полные».
63. Кэй (2000)
64. Аллан Скотт, Ульрике Стеге, Ирис ван Рой, Сапер, возможно, не являются NP-полными, но, тем не менее, сложно, Математический интеллект 33: 4 (2011), стр. 5–17.
65. Гэри и Джонсон (1979): GT56
66. Накаи, Кеничиро; Такенага, Ясухико (2012). «НП-Полнота пандемии». Журнал обработки информации. 20 (3): 723–726. Дои:10.2197 / ipsjjip.20.723. ISSN  1882-6652.
67. Демейн, Эрик; Айзенстат, Сара; Рудой, Михаил (2018). Оптимальное решение кубика Рубика является NP-полным. 35-й симпозиум по теоретическим аспектам информатики (STACS 2018). Дои:10.4230 / LIPIcs.STACS.2018.24.
68. http://pbg.cs.illinois.edu/papers/set.pdf
69. Сато, Такаяки; Сета, Такахиро (1987). Сложность и полнота поиска другого решения и его применение к головоломкам (PDF). Международный симпозиум по алгоритмам (SIGAL 1987).
70. Нукуи; Уэдзима (март 2007 г.). «Полнота ASP-головоломки скользящего звена на нескольких сетках». Примечания к Ipsj Sig. 2007 (23): 129–136.
71. Кёлькер, Йонас (2012). "Выбранные варианты Slither Link являются NP-завершенными". Журнал обработки информации. 20 (3): 709–712. Дои:10.2197 / ipsjjip.20.709.
72. ОБЗОР NP-ПОЛНЫХ ЗАДАЧ, Раздел 23; Грэм Кендалл, Эндрю Паркс, Кристиан Сперер; Март 2008 г. (icga2008.pdf)
73. Demaine, Eric D .; Хоэнбергер, Сьюзен; Либен-Новелл, Дэвид (25–28 июля 2003 г.). Тетрис - это сложно, даже приблизительно (PDF). Труды 9-й Международной конференции по вычислениям и комбинаторике (COCOON 2003). Большое небо, Монтана.
74. Лим, Эндрю (1998), "Проблема планирования причала", Письма об исследованиях операций, 22 (2–3): 105–110, Дои:10.1016 / S0167-6377 (98) 00010-8, МИСТЕР  1653377
75. Дж. Бонно: «Майнинг биткойнов - сложная задача.
76. Гэри и Джонсон (1979): LO1
77. Гэри и Джонсон (1979): п. 48
78. Гэри и Джонсон (1979): SR31
79. Гэри и Джонсон (1979): GT6
80. Минимальный независимый доминирующий набор
81. Гэри и Джонсон (1979): GT10
82. Гэри и Джонсон (1979): GT49
83. Гэри и Джонсон (1979): LO5
84. https://web.archive.org/web/20150203193923/http://www.meliksah.edu.tr/acivril/max-vol-original.pdf
85. Питер Дауни, Бентон Леонг и Рави Сетхи. "Вычислительные последовательности с дополнительными цепочками" SIAM J. Comput., 10 (3), 638–646, 1981
86. Д. Дж. Бернштейн "Алгоритм возведения в степень Пиппингера (проект)
87. Касивабара и Фудзисава (1979); Ohtsuki et al. (1979); Ленгауэр (1981).
88. Hurkens, C .; Iersel, L.V .; Keijsper, J .; Kelk, S .; Stougie, L .; Тромп, Дж. (2007). «Обращение префиксов к двоичным и троичным строкам». SIAM J. Дискретная математика. 21 (3): 592–611. arXiv:математика / 0602456. Дои:10.1137/060664252.
89. Гэри и Джонсон (1979): GT48
90. Гэри и Джонсон (1979): ND13
91. Гэри и Джонсон (1979): SP3
92. Гэри и Джонсон (1979): SR33
93. Bein, W. W .; Larmore, L.L .; Latifi, S .; Садборо, И. Х. (1 января 2002 г.). Сортировка блоков сложна. Международный симпозиум по параллельным архитектурам, алгоритмам и сетям, 2002. I-SPAN '02. Труды. С. 307–312. Дои:10.1109 / ISPAN.2002.1004305. ISBN  978-0-7695-1579-3. S2CID  32222403.
94. Барри Артур Сипра, "Модель Изинга является NP-полной", Новости SIAM, Том 33, № 6.

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

Общий

• Гарей, Майкл Р.; Джонсон, Дэвид С. (1979), Компьютеры и непреодолимость: руководство по теории NP-полноты, В. Х. Фриман, ISBN  0-7167-1045-5. Это классическая книга, развивающая теорию, затем каталогизирующая много НП-Полные задачи.
• Кук, С.А. (1971). «Сложность процедур доказательства теорем». Труды, Третий ежегодный симпозиум ACM по теории вычислений, ACM, Нью-Йорк. С. 151–158. Дои:10.1145/800157.805047.
• Карп, Ричард М. (1972). «Сводимость комбинаторных задач». В Miller, Raymond E .; Тэтчер, Джеймс У. (ред.). Сложность компьютерных вычислений. Пленум. С. 85–103.
• Данн, П. «Аннотированный список избранных NP-полных задач». COMP202, Департамент компьютерных наук, Ливерпульский университет. Получено 21 июн 2008.
• Crescenzi, P .; Канн, В .; Halldórsson, M .; Карпинский, М.; Woeginger, G. «Сборник задач оптимизации НП». KTH NADA, Стокгольм. Получено 21 июн 2008.
• Дальке, К. «NP-полные задачи». Справочный проект по математике. Получено 21 июн 2008.

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

• Фридман, E (2002). «Жемчужные головоломки NP-полны». Стетсонский университет, Деленд, Флорида. Получено 21 июн 2008.
• Григорьев А; Бодландер, H L (2007). «Алгоритмы для встраиваемых графов с несколькими пересечениями на ребро». Алгоритмика. 49 (1): 1–11. CiteSeerX  10.1.1.61.3576. Дои:10.1007 / s00453-007-0010-х. МИСТЕР  2344391. S2CID  8174422.
• Hartung, S; Нихтерлейн, А (2012). Как мир вычисляет. Конспект лекций по информатике. 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). «Сапер НП-комплектный». Математический интеллигент. 22 (2): 9–15. Дои:10.1007 / BF03025367. S2CID  122435790. Дополнительная информация доступна на сайте Страницы Сапера Ричарда Кея.
• Кашивабара, Т .; Фудзисава, Т. (1979). «NP-полнота задачи нахождения графа интервалов с минимальным кликовым числом, содержащего данный граф в качестве подграфа». Труды. Международный симпозиум по схемам и системам. С. 657–660.
• Оцуки, Тацуо; Мори, Хаджиму; Kuh, Ernest S .; Кашивабара, Тошинобу; Фудзисава, Тосио (1979). «Одномерные логические задания и интервальные графы». Транзакции IEEE в схемах и системах. 26 (9): 675–684. Дои:10.1109 / TCS.1979.1084695.
• Ленгауэр, Томас (1981). «Черно-белые камешки и разделение графиков». Acta Informatica. 16 (4): 465–475. Дои:10.1007 / BF00264496. S2CID  19415148.
• Арнборг, Стефан; Корнейл, Дерек Г.; Проскуровский, Анджей (1987). «Сложность поиска вложений в k-дерево". Журнал SIAM по алгебраическим и дискретным методам. 8 (2): 277–284. Дои:10.1137/0608024.
• Кормод, Грэм (2004). «Жесткость игры в лемминги, или О нет, еще доказательства NP-полноты». Труды Третьей Международной конференции по развлечениям с алгоритмами (FUN 2004). С. 65–76.

внешняя ссылка

• Сборник задач оптимизации NP
• График NP-полных задач