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

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

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

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

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

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

Набор вершин обратной связи ^[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-х разделах ^[3]^{: SP15}
Проблема упаковки контейнеров ^[3]^{: SR1}
Коммивояжер-пробник ^[3]^{: ND24}
Проблема расположения неиспользуемых объектов
Проблема планирования Flow Shop
Обобщенная задача о назначениях
Целочисленное программирование . Вариант, где переменные должны быть равны 0 или 1, называемый линейным программированием «ноль-один», и несколько других вариантов также являются NP-полными ^[2]^[3]^{: MP1}
Некоторые проблемы, связанные с планированием работы мастерской
Задача о рюкзаке , квадратная задача о рюкзаке и несколько вариантов ^[2]^[3]^{: MP9}
Некоторые проблемы, связанные с многопроцессорным планированием
Числовое 3-мерное сопоставление ^[3]^{: SP16}
График работы открытого цеха
Проблема с разделом ^[2]^[3]^{: SP12}
Квадратичная задача о назначениях ^[3]^{: ND43}
Квадратичное программирование (NP-трудное в некоторых случаях, P, если выпукло)
Задача о сумме подмножеств ^[3]^{: SP13}
Вариации задачи коммивояжера . Задача для графов является NP-полной, если длины ребер предполагаются целыми числами. Задача для точек на плоскости является NP-полной с дискретизированной евклидовой метрикой и прямолинейной метрикой. Известно, что задача является NP-трудной с (недискретизированной) евклидовой метрикой. ^[3]^{: ND22, ND23}

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

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

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

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

Другой

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

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

Примечания

^ Григорьев и Бодлендер (2007).
^ abcdefghijklmnopq Карп (1972)
^ abcdefghijklmnopqrstu vwxyz aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq ar as at au av aw ax ay az ba bb bc bd be Garey & Johnson (1979)
^ Минимальный независимый доминирующий набор
^ Брандес, Ульрик ; Деллинг, Даниэль; Гертлер, Марко; Гёрке, Роберт; Хёфер, Мартин; Николоски, Зоран; Вагнер, Доротея (2006), Максимизация модульности — это сложно , arXiv : physics/0608255 , Bibcode : 2006physics...8255B
^ ab Арнборг, Корнейл и Проскуровски (1987)
^ Касивабара и Фудзисава (1979); Оцуки и др. (1979); Ленгауэр (1981).
^ ab Garg, Ashim; Tamassia, Roberto (1995). "О вычислительной сложности проверки восходящей и прямолинейной планарности". Lecture Notes in Computer Science . Vol. 894/1995. pp. 286–297. doi :10.1007/3-540-58950-3_384. ISBN 978-3-540-58950-1.
^ Шефер, Маркус; Седжвик, Эрик; Штефанкович, Дэниел (сентябрь 2003 г.). «Распознавание строковых графов в NP». Журнал компьютерных и системных наук . 67 (2): 365–380. doi : 10.1016/S0022-0000(03)00045-X .
^ Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003), "Различение проблем выбора строк", Information and Computation , 185 (1): 41–55, doi : 10.1016/S0890-5401(03)00057-9 , MR 1994748
^ Вагнер, Роберт А. (май 1975 г.). «О сложности расширенной проблемы коррекции строк в строки». Труды седьмого ежегодного симпозиума ACM по теории вычислений — STOC '75 . стр. 218–223. doi :10.1145/800116.803771. ISBN 9781450374194. S2CID 18705107.
^ Фридман, Эрих. «Corral Puzzles are NP-complete» (PDF) . Получено 17 августа 2021 г.
^ Ято, Такауки (2003). Сложность и полнота нахождения другого решения и ее применение к головоломкам . CiteSeerX 10.1.1.103.8380 .
^ Мальте Хельмерт, Результаты сложности для стандартных контрольных областей в планировании, Искусственный интеллект 143(2):219-262, 2003.
^ «HASHIWOKAKERO — NP-полная задача».
^ Хольцер и Рюпп (2007)
^ Такахиро, Сета (5 февраля 2002 г.). «Сложности головоломок, перекрестных сумм и другие проблемы их решения (ASP)» (PDF) . Получено 18 ноября 2018 г.
^ Нгуен, Вьет-Ха; Перро, Кевин; Валле, Матье (24 июня 2020 г.). «NP-полнота игры KingdominoTM». Теоретическая информатика . 822 : 23–35. doi : 10.1016/j.tcs.2020.04.007 . ISSN 0304-3975. S2CID 218552723.
^ Кёлькер, Йонас (2012). «Kurodoko is NP-complete» (PDF) . Journal of Information Processing . 20 (3): 694–706. doi :10.2197/ipsjjip.20.694. S2CID 46486962. Архивировано из оригинала (PDF) 12 февраля 2020 г.
^ Александерссон, Пер; Рестад, Петтер (2020). «LaserTank is NP-Complete». Математические аспекты компьютерных и информационных наук . Конспект лекций по информатике. Том 11989. Springer International Publishing. С. 333–338. arXiv : 1908.05966 . doi :10.1007/978-3-030-43120-4_26. ISBN 978-3-030-43119-8. S2CID 201058355.
^ Кормод, Грэм (2004). Трудность игры в лемминги, или О нет, еще доказательства NP-полноты (PDF) .
^ Light Up — это NP-полная задача
^ Фридман, Эрих (27 марта 2012 г.). "Pearl Puzzles are NP-complete". Архивировано из оригинала 4 февраля 2012 г.
^ Кей (2000)
↑ Аллан Скотт, Ульрике Стеге, Айрис ван Рой, «Сапер», возможно, и не является NP-полной задачей, но тем не менее она трудна», The Mathematical Intelligencer 33 :4 (2011), стр. 5–17.
^ Хольцер, Маркус; Кляйн, Андреас; Кутриб, Мартин; Рюпп, Оливер (2011). «Вычислительная сложность NURIKABE». Fundamenta Informaticae . 110 (1–4): 159–174. doi :10.3233/FI-2011-534.
^ Накаи, Кенитиро; Такенага, Ясухико (2012). «НП-Завершенность пандемии». Журнал обработки информации . 20 (3): 723–726. дои : 10.2197/ipsjjip.20.723 . ISSN 1882-6652.
^ Демейн, Эрик; Эйзенштат, Сара; Рудой, Михаил (2018). Solving the Rubik's Cube Optimally is NP-complete . 35-й симпозиум по теоретическим аспектам компьютерной науки (STACS 2018). doi : 10.4230/LIPIcs.STACS.2018.24 .
^ ab Сато, Такаюки; Сета, Такахиро (1987). Сложность и полнота поиска другого решения и его применение к головоломкам (PDF) . Международный симпозиум по алгоритмам (SIGAL 1987).
^ Нукуи; Уэдзима (март 2007 г.). «ASP-полнота головоломки Slither Link на нескольких сетках». Ipsj Sig Notes . 2007 (23): 129–136.
^ Кёлькер, Йонас (2012). «Выбранные варианты Slither Link являются NP-полными». Журнал обработки информации . 20 (3): 709–712. doi : 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. doi : 10.1016/0304-3975(77)90005-6 .
^ Уитфилд, Джеймс Дэниел; Лав, Питер Джон; Аспуру-Гузик, Алан (2013). «Вычислительная сложность в электронной структуре». Phys. Chem. Chem. Phys . 15 (2): 397–411. arXiv : 1208.3334 . Bibcode :2013PCCP...15..397W. doi :10.1039/C2CP42695A. PMID 23172634. S2CID 12351374.
^ Агол, Ян ; Хасс, Джоэл ; Терстон, Уильям (19 мая 2002 г.). "3-многообразный род узлов является NP-полным". Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений . STOC '02. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 761–766. arXiv : math/0205057 . doi :10.1145/509907.510016. ISBN 978-1-58113-495-7. S2CID 10401375.
^ Чиврил, Али; Магдон-Исмаил, Малик (2009), «О выборе подматрицы максимального объема матрицы и связанных с этим проблемах» (PDF) , Теоретическая информатика , 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 Bernstein, «Алгоритм возведения в степень Пиппингера» (черновик)
^ Hurkens, C.; Iersel, LV; Keijsper, J.; Kelk, S.; Stougie, L.; Tromp, J. (2007). «Префиксные перестановки в двоичных и троичных строках». SIAM J. Discrete Math . 21 (3): 592–611. arXiv : math/0602456 . doi :10.1137/060664252.
^ ab Manders, Kenneth; Adleman, Leonard (1976). "NP-полные задачи принятия решений для квадратичных многочленов". Труды восьмого ежегодного симпозиума ACM по теории вычислений - STOC '76 . стр. 23–29. doi :10.1145/800113.803627. ISBN 9781450374149. S2CID 18885088.
^ Бейн, WW; Лармор, LL; Латифи, S.; Садборо, IH (1 января 2002 г.). «Сортировка блоков — это сложно». Труды Международного симпозиума по параллельным архитектурам, алгоритмам и сетям. I-SPAN'02 . стр. 307–312. doi :10.1109/ISPAN.2002.1004305. ISBN 978-0-7695-1579-3. S2CID 32222403.
↑ Барри Артур Сипра , «Модель Изинга NP-полна», SIAM News, том 33, № 6.

Ссылки

Общий

Garey, Michael R .; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455. MR 0519066. OCLC 247570676.. Эта книга является классической, развивающей теорию, а затем каталогизирующей многие NP-полные проблемы.
Кук, С.А. (1971). «Сложность процедур доказательства теорем». Труды Третьего ежегодного симпозиума ACM по теории вычислений, ACM, Нью-Йорк . С. 151–158. doi : 10.1145/800157.805047 .
Карп, Ричард М. (1972). «Сводимость среди комбинаторных задач». В Miller, Raymond E.; Thatcher, James W. (ред.). Complexity of Computer Computations . Plenum. стр. 85–103.
Данн, П.Е. "Аннотированный список избранных NP-полных задач". COMP202, Кафедра компьютерных наук, Ливерпульский университет . Получено 21 июня 2008 г.
Крещенци, П.; Канн, В.; Халлдорссон, М.; Карпински, М .; Вегингер, Г. «Сборник задач оптимизации NP». КТН НАДА, Стокгольм . Проверено 21 июня 2008 г.
Дальке, К. "NP-полные задачи". Math Reference Project . Получено 21 июня 2008 г.

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

Фридман, Э. (2002). «Pearl Puzzles are NP-complete». Университет Стетсона, ДеЛэнд, Флорида. Архивировано из оригинала 4 сентября 2006 г. Получено 21 июня 2008 г.
Григорьев, А; Бодлендер, ХЛ (2007). «Алгоритмы для графов, встраиваемых с небольшим количеством пересечений на ребро». Algorithmica . 49 (1): 1–11. CiteSeerX 10.1.1.61.3576 . doi :10.1007/s00453-007-0010-x. MR 2344391. S2CID 8174422.
Hartung, S; Nichterlein, A (2012). "NP-трудность и фиксированно-параметрическая управляемость реализации степенных последовательностей с направленными ациклическими графами". How the World Computes . Lecture Notes in Computer Science. Vol. 7318. Springer, Berlin, Heidelberg. pp. 283–292. CiteSeerX 10.1.1.377.2077 . doi :10.1007/978-3-642-30870-3_29. ISBN 978-3-642-30869-7. S2CID 6112925.
Хольцер, Маркус; Рюпп, Оливер (2007). «Проблемы дизайна интерьера — анализ сложности игры Heyawake» (PDF) . Труды 4-й Международной конференции по развлечениям с алгоритмами, LNCS 4475. Springer, Берлин/Гейдельберг. стр. 198–212. doi :10.1007/978-3-540-72914-3_18. ISBN 978-3-540-72913-6.
Кей, Ричард (2000). «Minesweeper is NP-complete». Mathematical Intelligencer . 22 (2): 9–15. doi :10.1007/BF03025367. S2CID 122435790.Дополнительную информацию можно найти в Интернете на страницах книги Ричарда Кея «Сапер».
Кашивабара, Т.; Фудзисава, Т. (1979). "NP-полнота задачи нахождения графа интервала с минимальным числом клик, содержащего заданный граф в качестве подграфа". Труды . Международный симпозиум по схемам и системам . С. 657–660.
Оцуки, Тацуо; Мори, Хаджиму; Кух, Эрнест С.; Кашивабара, Тошинобу; Фудзисава, Тошио (1979). «Одномерное назначение логических вентилей и интервальные графы». Труды IEEE по схемам и системам . 26 (9): 675–684. doi :10.1109/TCS.1979.1084695.
Ленгауэр, Томас (1981). «Черно-белые камешки и разделение графов». Acta Informatica . 16 (4): 465–475. doi :10.1007/BF00264496. S2CID 19415148.
Арнборг, Стефан; Корнейл, Дерек Г.; Проскуровски, Анджей (1987). «Сложность поиска вложений в k -дерево». Журнал SIAM по алгебраическим и дискретным методам . 8 (2): 277–284. doi :10.1137/0608024.
Кормод, Грэм (2004). «Трудность игры в леммингов, или О нет, еще больше доказательств NP-полноты». Труды Третьей международной конференции по развлечениям с алгоритмами (FUN 2004) . стр. 65–76.

Внешние ссылки

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