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

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

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

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

1-планарность
3-х мерное соответствие
Двудольное измерение
Емкостное минимальное остовное дерево
Задача проверки маршрута (также называемая проблемой китайского почтальона ) для смешанных графов (имеющих как направленные, так и неориентированные ребра). Программа разрешима за полиномиальное время, если в графе есть все неориентированные или все ориентированные ребра. Варианты включают задачу сельского почтальона.
Проблема с кликой
Полная окраска , также известная как ахроматическое число
Датический номер
Доминирующий набор , он же номер доминирования

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

Проблема с пропускной способностью
Проблема прикрытия клики
Раскраска рангов, также известная как ранг цикла
Остовное дерево с ограничениями по степени
Проблема с точным покрытием . Остается НП-комплектом для 3-х комплектов. Разрешается за полиномиальное время для 2-множеств (это совпадение ).
Набор вершин обратной связи
Дуга обратной связи установлена
Проблема гомоморфизма графов
Раскраска графика
Разбиение графа на подграфы определенных типов (треугольники, изоморфные подграфы , гамильтоновы подграфы, леса , совершенные сопоставления ) известны как NP-полные. Перегородка в клики это та же проблема , как окраска в дополнении данного графа. Связанная с этим проблема состоит в том, чтобы найти раздел, который является оптимальным с точки зрения количества ребер между частями.
Гамильтоново пополнение
Задача о гамильтоновом пути , направленном и неориентированном.
Проблема самого длинного пути
Максимальный двудольный подграф или (особенно со взвешенными ребрами) максимальный разрез .
Максимальный независимый набор
Максимальный индуцированный путь
Номер пересечения графика
Метрическое измерение графика
Минимальный k-разрез
Дерево Штейнера , или Минимальное остовное дерево для подмножества вершин графа. (Минимальное остовное дерево для всего графа разрешимо за полиномиальное время.)
Максимизация модульности
Ширина пути
Установить покрытие (также называемое проблемой минимального покрытия ) Это эквивалентно, транспонируя матрицу инцидентности, задаче попадания множества.
Задайте задачу разделения
Остовное дерево кратчайшей общей длины пути
Испытание на склоне номер два
Ширина дерева
Крышка Vertex

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

Проблема с 3 разделами
Проблема с упаковкой бункера
Задача о ранце , квадратичная задача о ранце и несколько вариантов
Варианты задачи коммивояжера . Проблема для графов является NP-полной, если длины ребер предполагаются целыми числами. Задача для точек на плоскости является NP-полной с дискретной евклидовой метрикой и прямолинейной метрикой. Известно, что проблема NP-трудна с (недискретизированной) евклидовой метрикой.
Коммивояжер с узким местом
Целочисленное программирование . Вариант, в котором переменные должны быть равны 0 или 1, называется линейным программированием нуля или единицы, а несколько других вариантов также являются NP-полными.
Латинские квадраты (проблема определения, можно ли заполнить частично заполненный квадрат, чтобы сформировать его)
Численное 3-мерное сопоставление
Проблема с разделом
Квадратичная задача о назначении
Решение квадратичных многочленов с двумя переменными над целыми числами. Даны положительные целые числа , найдите такие положительные числа , что $\textstyle A,B,C\geq 0$ $x,y$ $Ax^{2}+By-C=0$
Квадратичное программирование (NP-сложное в некоторых случаях, P, если выпуклое)
Проблема суммы подмножества

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

Ближайшая строка
Самая длинная общая проблема подпоследовательности по нескольким последовательностям
Ограниченный вариант задачи о переписке Поста.
Кратчайшая общая суперпоследовательность
Проблема исправления строки в строку

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

Сумка (Загон)
Линкор
Bulls and Cows , позиционируемые как Master Mind : определенные проблемы оптимизации, но не сама игра.
Вечность II
( Обобщенное ) FreeCell
Филломино
Хашивокакеро
Heyawake
( Общее ) Мгновенное безумие
Какуро (кросс-суммы)
Kingdomino
Куромасу (также известный как Куродоко)
LaserTank
Лемминги (с полиномиальным ограничением по времени)
Загораться
Масю
Проблема согласованности Minesweeper (но см. Scott, Stege, & van Rooij)
Нимбера (или число Гранди) ориентированного графа.
Номер ссылка
Нонограммы
Нурикабе
( Обобщенная ) Пандемия
Оптимальное решение для кубика Рубика $N \times N \times N$
SameGame
( Обобщенный ) Набор
Slither Link на различных сетках
( Обобщенное ) Судоку
Тентаи Шоу
Проблемы, связанные с тетрисом
Словесная арифметика

Другой

Проблема размещения причалов
Близость
Сборка оптимального блока биткойнов .
Проблема логической выполнимости (SAT). Есть много вариаций, которые также являются NP-полными. Важным вариантом является то, что каждое предложение имеет ровно три литерала (3SAT), поскольку оно используется в доказательстве многих других результатов NP-полноты.
Конъюнктивный логический запрос
Циклический заказ
Проблема выполнимости схемы
Проблема с расположением неработающего объекта
Проблема планирования производственного процесса
Обобщенная проблема присваивания
Тестирование восходящей планарности
Поиск глобального минимума раствора ХФ задачи
Проблема больниц и жителей с парами
Некоторые проблемы, связанные с планированием работы магазина
Монохромный треугольник
Минимальный максимальный независимый набор или минимальный независимый доминирующий набор

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

Проблема изоморфизма максимального общего подграфа
Остовное дерево минимальной степени
Минимальное k-остовное дерево
Метрический k-центр
Максимальная 2-выполнимость
Модальная логика S5-Выполнимость
Некоторые проблемы, связанные с многопроцессорным планированием
Подматрица максимального объема - проблема выбора наилучшего условного подмножества большей матрицы. Этот класс задач связан с определением ранга QR-факторизацией и оптимальным планом эксперимента D. $m\times n$
Минимальные цепочки сложения для последовательностей. Сложность минимальных цепочек сложения отдельных чисел неизвестна.
Нелинейные одномерные многочлены над GF [2 ⁿ ], n длина входа. Действительно, над любой GF [q ⁿ ].
Планирование открытых магазинов
Ширина пути , или, что то же самое, толщина интервала и число разделения вершин
Проблема расстояния сортировки блинов для строк
к-китайский почтальон
Проблема изоморфизма подграфов
Варианты задачи о дереве Штейнера . В частности, с дискретизированной евклидовой метрикой, прямолинейной метрикой. Как известно, проблема NP-трудна с (недискретизированной) евклидовой метрикой.
Набор упаковки
Сериализуемость историй базы данных
Планирование для минимизации взвешенного времени завершения
Разреженное приближение
Блочная сортировка (сортировка по перемещению блока)
Создание экземпляра второго порядка
Ширина дерева
Проверка того, может ли дерево быть представлено как евклидово минимальное остовное дерево
Трехмерная модель Изинга
Проблема с маршрутизацией автомобиля

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

Примечания

использованная литература

Общий

Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5. Эта классическая книга развивает теорию, а затем каталогизирует многие NP-Complete задачи.
Кук, SA (1971). «Сложность процедур доказательства теорем». Труды, Третий ежегодный симпозиум ACM по теории вычислений, ACM, Нью-Йорк . С. 151–158. DOI : 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 года .
Григорьев А; Bodlaender, HL (2007). «Алгоритмы для встраиваемых графов с несколькими пересечениями на ребро». Алгоритмика . 49 (1): 1–11. CiteSeerX 10.1.1.61.3576 . DOI : 10.1007 / s00453-007-0010-х . Руководство по ремонту 2344391 . S2CID 8174422 .
Hartung, S; Нихтерлейн, А (2012). Как мир вычисляет . Конспект лекций по информатике. 7318 . Шпрингер, Берлин, Гейдельберг. С. 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 . Шпрингер, Берлин / Гейдельберг. С. 198–212. DOI : 10.1007 / 978-3-540-72914-3_18 . ISBN 978-3-540-72913-6.
Кэй, Ричард (2000). «Сапер НП-комплектный». Математический интеллигент . 22 (2): 9–15. DOI : 10.1007 / BF03025367 . S2CID 122435790 .Дополнительная информация доступна в Интернете на страницах Сапера Ричарда Кея .
Kashiwabara, T .; Фудзисава, Т. (1979). «NP-полнота задачи поиска интервального графа с минимальным кликовым числом, содержащего данный граф в качестве подграфа». Ход работы . Международный симпозиум по схемам и системам . С. 657–660.
Оцуки, Тацуо; Мори, Хаджиму; Kuh, Ernest S .; Кашивабара, Тошинобу; Фудзисава, Тосио (1979). «Одномерные логические задания и интервальные графы». IEEE Transactions on Circuits and Systems . 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 -дерево». Журнал СИАМ по алгебраическим и дискретным методам . 8 (2): 277–284. DOI : 10.1137 / 0608024 .
Кормод, Грэм (2004). «Жесткость игры в лемминги, или О нет, еще доказательства NP-полноты». Труды Третьей Международной конференции по развлечениям с алгоритмами (FUN 2004) . С. 65–76.

Languages

In other projects