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-промежуточными

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

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

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

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

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

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

Теория игр

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

Графовые алгоритмы

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

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

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

Ссылки

^ Ладнер, Ричард (1975). «О структуре полиномиальной приводимости по времени» . Журнал АКМ . 22 (1): 155–171. дои : 10.1145/321864.321877 . S2CID 14352974 .
^ Гредель, Эрих; Колайтис, Фокион Г.; Либкин, Леонид; Маркс, Мартен; Спенсер, Джоэл ; Варди, Моше Ю .; Венема, Иде; Вайнштейн, Скотт (2007). Теория конечных моделей и ее приложения . Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag . п. 348. ИСБН 978-3-540-00428-8 . Збл 1133.03001 .
^ Шефер, Томас Дж. (1978). «Сложность задач выполнимости» (PDF) . Учеб. 10-я Энн. ACM симп. по теории вычислений . стр. 216–226. МР 0521057 .
^ Кишфалуди-Бак, Шандор (2020). «Гиперболические графы пересечений и (квази)-полиномиальное время». В Чавле, Шучи (ред.). Материалы 31-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2020, Солт-Лейк-Сити, Юта, США, 5–8 января 2020 г. стр. 1621–1638. arXiv : 1812.03960 . дои : 10.1137/1.9781611975994.100 . ISBN 978-1-61197-599-4 .
^ Эппштейн, Дэвид ; Линкольн, Андреа; Уильямс, Вирджиния Василевска (2023). «Квазиполиномиальность наименьшего отсутствующего индуцированного подграфа» . Журнал графовых алгоритмов и приложений . 27 (5): 329–339. arXiv : 2306.11185 . дои : 10.7155/jgaa.00625 .
^ Адлеман, Леонард; Мандерс, Кеннет (1977). «Сводимость, случайность и трудноразрешимость». Материалы 9-го симпозиума ACM. по теории вычислений (STOC '77) . дои : 10.1145/800105.803405 .
^ Пападимитриу, Христос Х. (1994). Вычислительная сложность . Аддисон-Уэсли. п. 236. ИСБН 9780201530827 .
^ Эйтер, Томас; Готтлоб, Георг (2002). «Трансверсальные вычисления гиперграфа и связанные с ними проблемы логики и искусственного интеллекта». Во Флеске, Серджио; Греко, Серджио; Леоне, Никола; Янни, Джовамбаттиста (ред.). Логика в искусственном интеллекте, Европейская конференция, JELIA 2002, Козенца, Италия, 23-26 сентября, Материалы . Конспекты лекций по информатике. Том. 2424. Спрингер. стр. 549–564. дои : 10.1007/3-540-45757-7_53 .
^ Кабанец, Валентин; Цай, Джин-И (2000). «Задача минимизации схемы». Учеб. 32-й симпозиум по теории вычислений . Портленд, Орегон, США. стр. 73–79. дои : 10.1145/335305.335314 . S2CID 785205 . ЕССС ТР99-045 .
^ Jump up to: ^а ^б Эйтер, Томас; Макино, Казухиса; Готтлоб, Георг (2008). «Вычислительные аспекты монотонной дуализации: краткий обзор» . Дискретная прикладная математика . 156 (11): 2035–2049. дои : 10.1016/j.dam.2007.04.017 . МР 2437000 . S2CID 10096898 .
^ Слитор, Дэниел Д.; Тарьян, Роберт Э.; Терстон, Уильям П. (1988). «Расстояние вращения, триангуляции и гиперболическая геометрия» . Журнал Американского математического общества . 1 (3): 647–681. дои : 10.2307/1990951 . JSTOR 1990951 . МР 0928904 .
^ Скиена, Стивен; Смит, Уоррен Д.; Лемке, Пол (1990). «Реконструкция множеств по расстояниям между точками (расширенное резюме)». В Зейделе, Раймунд (ред.). Материалы шестого ежегодного симпозиума по вычислительной геометрии, Беркли, Калифорния, США, 6-8 июня 1990 г. АКМ. стр. 332–339. дои : 10.1145/98524.98598 .
^ Янсен, Клаус; Солис-Оба, Роберто (2011). «Алгоритм OPT + 1 с полиномиальным временем для задачи резки материала с постоянным числом длин объектов». Математика исследования операций . 36 (4): 743–753. дои : 10.1287/moor.1110.0515 . МР 2855867 .
^ Лакенби, Марк (2021). «Эффективная сертификация узловатости и нормы Терстона» . Достижения в математике . 387 : Документ № 107796. arXiv : 1604.00290 . дои : 10.1016/j.aim.2021.107796 . МР 4274879 . S2CID 119307517 .
^ Демейн, Эрик Д .; О'Рурк, Джозеф (2007). «24 геодезические: Люстерник – Шнирельман». Алгоритмы геометрического складывания: Связи, оригами, многогранники . Кембридж: Издательство Кембриджского университета. стр. 372–375. дои : 10.1017/CBO9780511735172 . ISBN 978-0-521-71522-5 . МР 2354878 . .
^ Юрдзинский, Марцин (1998). «Определение победителя в паритетных играх происходит в УП $\cap$ co-UP». Письма об обработке информации . 68 (3): 119–124. doi : 10.1016/S0020-0190(98)00150-1 . MR 1657581 .
^ Кондон, Энн (1992). «Сложность стохастических игр» . Информация и вычисления . 96 (2): 203–224. дои : 10.1016/0890-5401(92)90048-К . МР 1147987 .
^ Гроэ, Мартин; Нойен, Даниэль (июнь 2021 г.). «Последние достижения в проблеме изоморфизма графов». Обзоры по комбинаторике 2021 . Издательство Кембриджского университета. стр. 187–234. arXiv : 2011.01366 . дои : 10.1017/9781009036214.006 . S2CID 226237505 .
^ Jump up to: ^а ^б Матон, Р. (1979). «Заметка о проблеме подсчета изоморфизма графов». Письма об обработке информации . 8 (3): 131–132. дои : 10.1016/0020-0190(79)90004-8 .
^ Карпински, Марек (2002). «Аппроксимируемость задачи минимального деления пополам: алгоритмическая задача». В Диксе, Кшиштоф; Риттер, Войцех (ред.). Математические основы информатики, 2002 г., 27-й международный симпозиум, MFCS 2002, Варшава, Польша, 26–30 августа 2002 г., Труды . Конспекты лекций по информатике. Том. 2420. Спрингер. стр. 59–67. дои : 10.1007/3-540-45687-2_4 .
^ Галлиан, Джозеф А. (17 декабря 2021 г.). «Динамический обзор разметки графов» . Электронный журнал комбинаторики . 5 : Динамическое обследование 6. MR 1668059 .
^ Нисимура, Н.; Рагде, П.; Тиликос, DM (2002). «О степенях графа для деревьев, помеченных листьями». Журнал алгоритмов . 42 : 69–108. дои : 10.1006/jagm.2001.1195 . .
^ Товарищи, Майкл Р .; Розамонд, Фрэнсис А .; Ротикс, Уди; Зейдер, Стефан (2009). «Ширина клики NP-полная». SIAM Journal по дискретной математике . 23 (2): 909–939. дои : 10.1137/070687256 . МР 2519936 . .
^ Гасснер, Элизабет; Юнгер, Майкл; Перкан, Мериям; Шефер, Маркус; Шульц, Майкл (2006). «Одновременные вложения графов с фиксированными ребрами». Теоретико-графовые концепции в информатике: 32-й международный семинар, WG 2006, Берген, Норвегия, 22–24 июня 2006 г., Пересмотренные статьи (PDF) . Конспекты лекций по информатике. Том. 4271. Берлин: Шпрингер. стр. 325–335. дои : 10.1007/11917496_29 . МР 2290741 . .
^ Пападимитриу, Христос Х .; Яннакакис, Михалис (1996). «Об ограниченном недетерминизме и сложности измерения VC» . Журнал компьютерных и системных наук . 53 (2, часть 1): 161–170. дои : 10.1006/jcss.1996.0058 . МР 1418886 .

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

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

[1] Ладнер, Ричард (1975). «О структуре полиномиальной приводимости по времени» . Журнал АКМ . 22 (1): 155–171. дои : 10.1145/321864.321877 . S2CID 14352974 .

[2] Гредель, Эрих; Колайтис, Фокион Г.; Либкин, Леонид; Маркс, Мартен; Спенсер, Джоэл ; Варди, Моше Ю .; Венема, Иде; Вайнштейн, Скотт (2007). Теория конечных моделей и ее приложения . Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag . п. 348. ИСБН 978-3-540-00428-8 . Збл 1133.03001 .

[3] Шефер, Томас Дж. (1978). «Сложность задач выполнимости» (PDF) . Учеб. 10-я Энн. ACM симп. по теории вычислений . стр. 216–226. МР 0521057 .

[4] Кишфалуди-Бак, Шандор (2020). «Гиперболические графы пересечений и (квази)-полиномиальное время». В Чавле, Шучи (ред.). Материалы 31-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2020, Солт-Лейк-Сити, Юта, США, 5–8 января 2020 г. стр. 1621–1638. arXiv : 1812.03960 . дои : 10.1137/1.9781611975994.100 . ISBN 978-1-61197-599-4 .

[5] Эппштейн, Дэвид ; Линкольн, Андреа; Уильямс, Вирджиния Василевска (2023). «Квазиполиномиальность наименьшего отсутствующего индуцированного подграфа» . Журнал графовых алгоритмов и приложений . 27 (5): 329–339. arXiv : 2306.11185 . дои : 10.7155/jgaa.00625 .

[6] Адлеман, Леонард; Мандерс, Кеннет (1977). «Сводимость, случайность и трудноразрешимость». Материалы 9-го симпозиума ACM. по теории вычислений (STOC '77) . дои : 10.1145/800105.803405 .

[7] Пападимитриу, Христос Х. (1994). Вычислительная сложность . Аддисон-Уэсли. п. 236. ИСБН 9780201530827 .

[8] Эйтер, Томас; Готтлоб, Георг (2002). «Трансверсальные вычисления гиперграфа и связанные с ними проблемы логики и искусственного интеллекта». Во Флеске, Серджио; Греко, Серджио; Леоне, Никола; Янни, Джовамбаттиста (ред.). Логика в искусственном интеллекте, Европейская конференция, JELIA 2002, Козенца, Италия, 23-26 сентября, Материалы . Конспекты лекций по информатике. Том. 2424. Спрингер. стр. 549–564. дои : 10.1007/3-540-45757-7_53 .

[9] Кабанец, Валентин; Цай, Джин-И (2000). «Задача минимизации схемы». Учеб. 32-й симпозиум по теории вычислений . Портленд, Орегон, США. стр. 73–79. дои : 10.1145/335305.335314 . S2CID 785205 . ЕССС ТР99-045 .

[emg-10] Jump up to: ^а ^б Эйтер, Томас; Макино, Казухиса; Готтлоб, Георг (2008). «Вычислительные аспекты монотонной дуализации: краткий обзор» . Дискретная прикладная математика . 156 (11): 2035–2049. дои : 10.1016/j.dam.2007.04.017 . МР 2437000 . S2CID 10096898 .

[11] Слитор, Дэниел Д.; Тарьян, Роберт Э.; Терстон, Уильям П. (1988). «Расстояние вращения, триангуляции и гиперболическая геометрия» . Журнал Американского математического общества . 1 (3): 647–681. дои : 10.2307/1990951 . JSTOR 1990951 . МР 0928904 .

[12] Скиена, Стивен; Смит, Уоррен Д.; Лемке, Пол (1990). «Реконструкция множеств по расстояниям между точками (расширенное резюме)». В Зейделе, Раймунд (ред.). Материалы шестого ежегодного симпозиума по вычислительной геометрии, Беркли, Калифорния, США, 6-8 июня 1990 г. АКМ. стр. 332–339. дои : 10.1145/98524.98598 .

[13] Янсен, Клаус; Солис-Оба, Роберто (2011). «Алгоритм OPT + 1 с полиномиальным временем для задачи резки материала с постоянным числом длин объектов». Математика исследования операций . 36 (4): 743–753. дои : 10.1287/moor.1110.0515 . МР 2855867 .

[14] Лакенби, Марк (2021). «Эффективная сертификация узловатости и нормы Терстона» . Достижения в математике . 387 : Документ № 107796. arXiv : 1604.00290 . дои : 10.1016/j.aim.2021.107796 . МР 4274879 . S2CID 119307517 .

[15] Демейн, Эрик Д .; О'Рурк, Джозеф (2007). «24 геодезические: Люстерник – Шнирельман». Алгоритмы геометрического складывания: Связи, оригами, многогранники . Кембридж: Издательство Кембриджского университета. стр. 372–375. дои : 10.1017/CBO9780511735172 . ISBN 978-0-521-71522-5 . МР 2354878 . .

[16] Юрдзинский, Марцин (1998). «Определение победителя в паритетных играх происходит в УП $\cap$ co-UP». Письма об обработке информации . 68 (3): 119–124. doi : 10.1016/S0020-0190(98)00150-1 . MR 1657581 .

[17] Кондон, Энн (1992). «Сложность стохастических игр» . Информация и вычисления . 96 (2): 203–224. дои : 10.1016/0890-5401(92)90048-К . МР 1147987 .

[18] Гроэ, Мартин; Нойен, Даниэль (июнь 2021 г.). «Последние достижения в проблеме изоморфизма графов». Обзоры по комбинаторике 2021 . Издательство Кембриджского университета. стр. 187–234. arXiv : 2011.01366 . дои : 10.1017/9781009036214.006 . S2CID 226237505 .

[mathon-19] Jump up to: ^а ^б Матон, Р. (1979). «Заметка о проблеме подсчета изоморфизма графов». Письма об обработке информации . 8 (3): 131–132. дои : 10.1016/0020-0190(79)90004-8 .

[20] Карпински, Марек (2002). «Аппроксимируемость задачи минимального деления пополам: алгоритмическая задача». В Диксе, Кшиштоф; Риттер, Войцех (ред.). Математические основы информатики, 2002 г., 27-й международный симпозиум, MFCS 2002, Варшава, Польша, 26–30 августа 2002 г., Труды . Конспекты лекций по информатике. Том. 2420. Спрингер. стр. 59–67. дои : 10.1007/3-540-45687-2_4 .

[21] Галлиан, Джозеф А. (17 декабря 2021 г.). «Динамический обзор разметки графов» . Электронный журнал комбинаторики . 5 : Динамическое обследование 6. MR 1668059 .

[22] Нисимура, Н.; Рагде, П.; Тиликос, DM (2002). «О степенях графа для деревьев, помеченных листьями». Журнал алгоритмов . 42 : 69–108. дои : 10.1006/jagm.2001.1195 . .

[23] Товарищи, Майкл Р .; Розамонд, Фрэнсис А .; Ротикс, Уди; Зейдер, Стефан (2009). «Ширина клики NP-полная». SIAM Journal по дискретной математике . 23 (2): 909–939. дои : 10.1137/070687256 . МР 2519936 . .

[24] Гасснер, Элизабет; Юнгер, Майкл; Перкан, Мериям; Шефер, Маркус; Шульц, Майкл (2006). «Одновременные вложения графов с фиксированными ребрами». Теоретико-графовые концепции в информатике: 32-й международный семинар, WG 2006, Берген, Норвегия, 22–24 июня 2006 г., Пересмотренные статьи (PDF) . Конспекты лекций по информатике. Том. 4271. Берлин: Шпрингер. стр. 325–335. дои : 10.1007/11917496_29 . МР 2290741 . .

[25] Пападимитриу, Христос Х .; Яннакакис, Михалис (1996). «Об ограниченном недетерминизме и сложности измерения VC» . Журнал компьютерных и системных наук . 53 (2, часть 1): 161–170. дои : 10.1006/jcss.1996.0058 . МР 1418886 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]