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-промежуточных, - это изоморфизма графов , а также варианты решения факторизации проблема и дискретного логарифма .

Список проблем, которые могут быть NP-промежуточными [ править ]

Алгебра и теория чисел [ править ]

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

Булева логика [ править ]

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

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

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

Теория игр [ править ]

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

Алгоритмы графов [ править ]

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

Разное [ править ]

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

Ссылки [ править ]

^ Ладнер, Ричард (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 .
^ Адлеман, Леонард; Мандерс, Кеннет (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 .
^ Карпински, Марек (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] Адлеман, Леонард; Мандерс, Кеннет (1977). «Сводимость, случайность и трудноразрешимость». Материалы 9-го симпозиума ACM. по теории вычислений (STOC '77) . дои : 10.1145/800105.803405 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[22] Пападимитриу, Христос Х .; Яннакакис, Михалис (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]