NP-промежуточный

Класс сложности задач

В вычислительной сложности задачи, которые находятся в классе сложности NP , но не являются ни классом P , ни NP-полными, называются NP-промежуточными , а класс таких задач называется NPI . Теорема Ладнера , показанная в 1975 году Ричардом Э. Ладнером [ ^1], является результатом, утверждающим, что если P ≠ NP , то NPI не пуст; то есть NP содержит задачи, которые не являются ни P, ни NP-полными. Поскольку также верно, что если существуют задачи NPI, то P ≠ NP, отсюда следует, что P = NP тогда и только тогда, когда NPI пуст.

При предположении, что P ≠ NP, Ладнер явно конструирует задачу в NPI, хотя эта задача искусственная и в остальном неинтересная. Остается открытым вопрос, обладает ли любая «естественная» задача тем же свойством: теорема Шефера о дихотомии предоставляет условия, при которых классы проблем ограниченной булевой выполнимости не могут быть в NPI. [ ^{2] [3]} Некоторые задачи, которые считаются хорошими кандидатами на то, чтобы быть NP-промежуточными, — это задача изоморфизма графов и версии решений факторизации и дискретного логарифма .

Согласно гипотезе об экспоненциальном времени , существуют естественные задачи, требующие квазиполиномиального времени и которые могут быть решены за это время, включая нахождение большого непересекающегося множества единичных дисков из заданного множества дисков в гиперболической плоскости ^[4] и нахождение графа с небольшим количеством вершин, который не является индуцированным подграфом заданного графа. ^[5] Гипотеза об экспоненциальном времени также подразумевает, что ни одна задача с квазиполиномиальным временем не может быть NP-полной, поэтому при этом предположении эти задачи должны быть NP-промежуточными.

Список задач, которые могут быть NP-промежуточными

Алгебра и теория чисел

• Вариант решения факторизации целых чисел : для входных данных и имеет ли множитель в интервале ? ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle [2,k]}$
• Версии решения задачи дискретного логарифмирования и другие, связанные с криптографическими предположениями
• Линейная делимость: даны целые числа и , есть ли делитель, сравнимый с 1 по модулю ? ^{[6] [7]} ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$

Булева логика

• IMSAT, булева задача выполнимости для «пересекающейся монотонной КНФ»: конъюнктивная нормальная форма , в которой каждое предложение содержит только положительные или только отрицательные члены, а каждое положительное предложение имеет общую переменную с каждым отрицательным предложением ^[8]
• Проблема минимального размера схемы : если дана таблица истинности булевой функции и положительное целое число , существует ли схема размера не более для этой функции? ^[9] ${\displaystyle s}$ ${\displaystyle s}$
• Монотонная дуализация : если даны формулы CNF и DNF для монотонных булевых функций, представляют ли они одну и ту же функцию? ^[10]
• Монотонная самодвойственность: если задана формула CNF для булевой функции, является ли функция инвариантной относительно преобразования, которое отрицает все ее переменные, а затем отрицает выходное значение? ^[10]

Вычислительная геометрия и вычислительная топология

• Определение того, является ли расстояние поворота ^[11] между двумя бинарными деревьями или расстояние переворота между двумя триангуляциями одного и того же выпуклого многоугольника ниже заданного порогового значения
• Задача магистрали по восстановлению точек на линии по их мультимножеству расстояний ^[12]
• Задача раскроя с постоянным числом длин объектов ^[13]
• Тривиальность узла ^[14]
• Нахождение простой замкнутой квазигеодезической на выпуклом многограннике ^[15]

Теория игр

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

Графические алгоритмы

• Проблема изоморфизма графов ^[18]
• Нахождение группы автоморфизмов графа ^[19]
• Нахождение числа автоморфизмов графа ^[19]
• Минимальная плоская бисекция ^[20]
• Определение того, допускает ли граф изящную маркировку ^[21]
• Распознавание листовых мощностей и k -листовых мощностей ^[22]
• Распознавание графов ограниченной кликовой ширины ^[23]
• Проверка существования одновременного вложения с фиксированными краями ^[24]

Разнообразный

• Проверка того, находится ли размерность Вапника–Червоненкиса заданного семейства множеств ниже заданной границы ^[25]

Ссылки

1. Ладнер, Ричард (1975). «О структуре полиномиальной приводимости по времени». Журнал ACM . 22 (1): 155–171. doi : 10.1145/321864.321877 . S2CID  14352974.
2. Грэдель, Эрих; Колайтис, Фокион Г.; Либкин, Леонид; Маркс, Маартен; Спенсер, Джоэл ; Варди, Моше Й .; Венема, Иде; Вайнштейн, Скотт (2007). Теория конечных моделей и ее приложения . Тексты по теоретической информатике. Серия EATCS. ​​Берлин: Springer-Verlag . стр. 348. ISBN 978-3-540-00428-8. Збл  1133.03001.
3. Шефер, Томас Дж. (1978). «Сложность проблем выполнимости» (PDF) . Proc. 10th Ann. ACM Symp. on Theory of Computing . стр. 216–226. MR  0521057.
4. Kisfaludi-Bak, Sándor (2020). «Гиперболические графы пересечений и (квази)полиномиальное время». В Chawla, Shuchi (ред.). Труды 31-го ежегодного симпозиума ACM–SIAM по дискретным алгоритмам, SODA 2020, Солт-Лейк-Сити, Юта, США, 5–8 января 2020 г. . стр. 1621–1638. arXiv : 1812.03960 . doi :10.1137/1.9781611975994.100. ISBN 978-1-61197-599-4.
5. Эппштейн, Дэвид ; Линкольн, Андреа; Уильямс, Вирджиния Василевска (2023). «Квазиполиномиальность наименьшего отсутствующего индуцированного подграфа». Журнал графовых алгоритмов и приложений . 27 (5): 329–339. arXiv : 2306.11185 . doi : 10.7155/jgaa.00625 .
6. Адлеман, Леонард; Мандерс, Кеннет (1977). «Сводимость, случайность и неподатливость». Труды 9-го симпозиума ACM по теории вычислений (STOC '77) . doi :10.1145/800105.803405.
7. Пападимитриу, Христос Х. (1994). Вычислительная сложность . Эддисон-Уэсли. стр. 236. ISBN 9780201530827.
8. Эйтер, Томас; Готтлоб, Георг (2002). «Трансверсальное вычисление гиперграфа и связанные с ним проблемы в логике и ИИ». В Flesca, Серджио; Греко, Серджио; Леоне, Никола; Янни, Джовамбаттиста (ред.). Логика в искусственном интеллекте, Европейская конференция, JELIA 2002, Козенца, Италия, 23–26 сентября, Труды . Заметки лекций по информатике. Том 2424. Springer. стр. 549–564. doi :10.1007/3-540-45757-7_53.
9. Кабанец, Валентин; Цай, Цзинь-И (2000). «Проблема минимизации цепей». Труды 32-го симпозиума по теории вычислений . Портленд, Орегон, США. стр. 73–79. doi : 10.1145/335305.335314 . S2CID  785205. ECCC  TR99-045.
10. Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008). «Вычислительные аспекты монотонной дуализации: краткий обзор». Discrete Applied Mathematics . 156 (11): 2035–2049. doi : 10.1016/j.dam.2007.04.017 . MR  2437000. S2CID  10096898.
11. Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). «Расстояние вращения, триангуляции и гиперболическая геометрия». Журнал Американского математического общества . 1 (3): 647–681. doi : 10.2307/1990951 . JSTOR  1990951. MR  0928904.
12. Скиена, Стивен; Смит, Уоррен Д.; Лемке, Пол (1990). «Реконструкция множеств по межточечным расстояниям (расширенный реферат)». В Seidel, Raimund (ред.). Труды шестого ежегодного симпозиума по вычислительной геометрии, Беркли, Калифорния, США, 6-8 июня 1990 г. ACM. стр. 332–339. doi : 10.1145/98524.98598 .
13. Янсен, Клаус; Солис-Оба, Роберто (2011). «Алгоритм OPT + 1 с полиномиальным временем для задачи раскроя с постоянным числом длин объектов». Математика исследования операций . 36 (4): 743–753. doi :10.1287/moor.1110.0515. MR  2855867.
14. Lackenby, Marc (2021). «Эффективная сертификация узловатости и нормы Терстона». Advances in Mathematics . 387 : Paper No. 107796. arXiv : 1604.00290 . doi : 10.1016/j.aim.2021.107796 . MR  4274879. S2CID  119307517.
15. Demaine, Erik D. ; O'Rourke, Joseph (2007). "24 Geodesics: Lyusternik–Schnirelmann". Геометрические алгоритмы складывания: связи, оригами, многогранники . Cambridge: Cambridge University Press. стр. 372–375. doi :10.1017/CBO9780511735172. ISBN 978-0-521-71522-5. МР  2354878..
16. Юрдзински, Марцин (1998). «Определение победителя в играх на равенство происходит в UP co-UP». Information Processing Letters . 68 (3): 119–124. doi :10.1016/S0020-0190(98)00150-1. MR  1657581. ${\displaystyle \cap }$
17. Кондон, Энн (1992). «Сложность стохастических игр». Информация и вычисления . 96 (2): 203–224. doi : 10.1016/0890-5401(92)90048-K . MR  1147987.
18. Гроэ, Мартин; Нойен, Дэниел (июнь 2021 г.). «Последние достижения в проблеме изоморфизма графов». Surveys in Combinatorics 2021. Cambridge University Press. стр. 187–234. arXiv : 2011.01366 . doi : 10.1017/9781009036214.006. S2CID  226237505.
19. Mathon, R. (1979). «Заметка о проблеме подсчета изоморфизма графов». Information Processing Letters . 8 (3): 131–132. doi :10.1016/0020-0190(79)90004-8.
20. Карпински, Марек (2002). «Аппроксимируемость минимальной проблемы бисекции: алгоритмический вызов». В Diks, Krzysztof; Rytter, Wojciech (ред.). Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings . Lecture Notes in Computer Science. Vol. 2420. Springer. pp. 59–67. doi :10.1007/3-540-45687-2_4.
21. Галлиан, Джозеф А. (17 декабря 2021 г.). «Динамический обзор маркировки графов». Электронный журнал комбинаторики . 5 : Динамический обзор 6. MR  1668059.
22. Нишимура, Н.; Рагде, П.; Тиликос, Д.М. (2002). «О степенях графов для деревьев с метками листьев». Журнал алгоритмов . 42 : 69–108. doi :10.1006/jagm.2001.1195..
23. Fellows, Michael R. ; Rosamond, Frances A. ; Rotics, Udi; Szeider, Stefan (2009). «Clique-width is NP-complete». SIAM Journal on Discrete Mathematics . 23 (2): 909–939. doi :10.1137/070687256. MR  2519936..
24. Гасснер, Элизабет; Юнгер, Михаэль; Перкан, Мериам; Шефер, Маркус; Шульц, Михаэль (2006). «Одновременные вложения графов с фиксированными ребрами». Графовые теоретические концепции в информатике: 32-й международный семинар, WG 2006, Берген, Норвегия, 22–24 июня 2006 г., пересмотренные статьи (PDF) . Lecture Notes in Computer Science. Vol. 4271. Berlin: Springer. pp. 325–335. doi :10.1007/11917496_29. MR  2290741..
25. Пападимитриу, Христос Х.; Яннакакис , Михалис (1996). «Об ограниченном недетерминизме и сложности измерения VC». Журнал компьютерных и системных наук . 53 (2, часть 1): 161–170. doi : 10.1006/jcss.1996.0058 . MR  1418886.

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

• Сложность зоопарка : Класс NPI
• Базовая структура, сводимость по Тьюрингу и NP-трудность
• Лэнс Фортноу (24 марта 2003 г.). "Основы сложности, Урок 16: Теорема Ладнера" . Получено 1 ноября 2013 г.