Список неполных неполадок

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

• 1 Графики и гиперграфы
• 2 Математическое программирование
• 3 Формальные языки и обработка строк
• 4 Игры и головоломки
• 5 Другое
• 6 См. также
• 7 Примечания
• 8 Ссылки
• 9 Внешние ссылки

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

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

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

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

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

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

• Морской бой
• Быки и коровы, позиционируется как Master Mind : некоторые проблемы оптимизации, но не сама игра.
• Eternity II
• (Generalized ) FreeCell
• Fillomino
• Hashiwokakero
• Heyawake
• (Generalized ) Мгновенное безумие
• Какуро (кросс-суммы)
• Кингардино
• Куромасу (также известный как Куродоко)
• LaserTank
• Лемминги (с полиномом ограничение по времени)
• Загорится
• Масю
• Проблема согласованности сапера (но см. Scott, Stege, van Rooij)
• Нимбер (или число Гранди) ориентированного графа.
• Numberlink
• Nonograms
• Nurikabe
• (Generalized ) Pandemic
• Оптимальное решение для N × N × N Кубика Рубика
• SameGame
• (Generalized ) Установите
• Slither Link на различных сетках
• (Generalized ) Sudoku
• Проблемы, связанные с Tetris
• Устная арифметика

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

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

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

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

Общие

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

Конкретные задачи

• Friedman, E (2002). «Pearl puzzles NP-complete». Stetson University, DeLand, Florida. Проверено 21 июня 2008.
• Григорьев, A; Бодлендер, HL (2007). «Алгоритмы для графов, встраиваемых с небольшим количеством пересечений на ребро». Algorithmica. 49 (1): 1–11. CiteSeerX 10.1.1.61.3576. doi : 10.1007 / s00453-007-0010-x. MR 2344391. S2CID 8174422. CS1 maint: ref = harv (ссылка )
• Hartung, S; Nichterlein, A (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. CS1 maint: ref = harv (ссылка )
• Кай, Ричард (2000). «Сапер - это NP-complete ». Mathematical Intelligencer. 22 (2): 9–15. doi : 10.1007 / BF03025367. S2CID 122435790. CS1 maint: ref = harv (ссылка ) Дополнительная информация доступна в Интернете на страницах «Сапер» Ричарда Кея.
• Kashiwabara, T.; Fujisawa, T.. (1979). «NP-полнота проблемы нахождения графа интервалов минимального числа кликов, содержащего данный граф в качестве подграфа». Труды. Международный симпозиум по схемам и системам. С. 657– 660. CS1 maint: ref = harv (ссылка )
• Охцуки, Тацуо; Мори, Хаджиму; Кух, Эрнест С.; Кашивабара, Тошинобу; Фудзисава, Тошио (1979). «Одномерные логические ворота графики назначений и интервалов ». IEEE Transactions on Circuits and Systems. 26 (9): 675–684. doi : 10.1109 / TCS.1979.1084695. CS1 maint: ref = harv (ссылка )
• Ленгауэр, Томас (1981). "Blac k-белые камешки и разделение графиков ». Acta Informatica. 16(4): 465–475. doi : 10.1007 / BF00264496. S2CID 19415148. CS1 maint: ref = harv (ссылка )
• Арнборг, Стефан; Корнейл, Дерек Г. ; Проскуровски, Анджей (1987). «Сложность поиска вложений в k-дереве». SIAM Journal on Algebraic and Discrete Methods. 8 (2): 277–284. doi : 10.1137 / 0608024. CS1 maint: ref = harv (ссылка )
• Cormode, Graham (2004). «Жесткость игры в лемминги, или О нет, еще несколько доказательств NP-полноты». Труды Третьей Международной конференции по развлечениям с алгоритмами (FUN 2004), стр. 65–76.

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