НП-средний - NP-intermediate - Wikipedia

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

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

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

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

Логическая логика

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

Теория игры

  • Определение победителя в паритетные игры[17]
  • Определение того, у кого больше шансов на победу в стохастической игре[17]
  • Контроль повестки дня сбалансированных турниров на выбывание[18]

Алгоритмы графа

Разное

  • Предполагая NEXP не равно EXP, дополненные версии проблем NEXP-complete
  • Проблемы в TFNP[24]
  • Сумма подмножества голубятни[25]
  • Нахождение Размер ВК[26]

Рекомендации

  1. ^ Ладнер, Ричард (1975). «О структуре полиномиальной сводимости». Журнал ACM. 22 (1): 155–171. Дои:10.1145/321864.321877. S2CID  14352974.
  2. ^ Грэдель, Эрих; Колайтис, Phokion G .; Либкин, Леонид; Маркс, Маартен; Спенсер, Джоэл; Варди, Моше Ю.; Венема, Иде; Вайнштейн, Скотт (2007). Теория конечных моделей и ее приложения. Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag. п. 348. ISBN  978-3-540-00428-8. Zbl  1133.03001.
  3. ^ Шефер, Томас Дж. (1978). «Сложность проблемы выполнимости» (PDF). Proc. 10-я Ann. ACM Symp. по теории вычислений. С. 216–226. МИСТЕР  0521057.
  4. ^ а б «Проблемы между P и NPC». Обмен стеками по теоретической информатике. 20 августа 2011 г.. Получено 1 ноября 2013.
  5. ^ http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html
  6. ^ https://cstheory.stackexchange.com/q/4331
  7. ^ https://cstheory.stackexchange.com/q/1739
  8. ^ https://cstheory.stackexchange.com/q/1745
  9. ^ Кабанец, Валентин; Цай, Цзинь-И (2000), "Задача минимизации схемы", Proc. 32-й симпозиум по теории вычислений, Портленд, Орегон, США, стр. 73–79, Дои:10.1145/335305.335314, S2CID  785205, ECCC  TR99-045
  10. ^ https://cstheory.stackexchange.com/q/3950
  11. ^ Расстояние вращения, триангуляции и гиперболическая геометрия
  12. ^ Реконструкция наборов из межточечных расстояний
  13. ^ https://cstheory.stackexchange.com/q/3827
  14. ^ https://cstheory.stackexchange.com/q/1106
  15. ^ https://cstheory.stackexchange.com/q/7806
  16. ^ Демейн, Эрик Д.; О'Рурк, Джозеф (2007), «24 геодезических: Люстерник – Шнирельманн», Алгоритмы геометрического складывания: Связи, оригами, многогранники, Кембридж: Издательство Кембриджского университета, стр. 372–375, Дои:10.1017 / CBO9780511735172, ISBN  978-0-521-71522-5, МИСТЕР  2354878.
  17. ^ а б http://kintali.wordpress.com/2010/06/06/np-intersect-conp/
  18. ^ https://cstheory.stackexchange.com/q/460
  19. ^ Аппроксимируемость задачи минимального деления пополам: алгоритмическая проблема
  20. ^ https://cstheory.stackexchange.com/q/6384
  21. ^ Nishimura, N .; Ragde, P .; Тиликос, Д. (2002), "О степенях графа для деревьев с листами", Журнал алгоритмов, 42: 69–108, Дои:10.1006 / jagm.2001.1195.
  22. ^ Товарищи, Майкл Р.; Розамонд, Фрэнсис А.; Ротикс, Уди; Зейдер, Стефан (2009), «Ширина клики NP-полная», Журнал SIAM по дискретной математике, 23 (2): 909–939, Дои:10.1137/070687256, МИСТЕР  2519936.
  23. ^ Гасснер, Элизабет; Юнгер, Михаэль; Percan, Merijam; Шефер, Маркус; Шульц, Майкл (2006), "Одновременные вложения графов с фиксированными ребрами", Теоретико-графические концепции в компьютерных науках: 32-й международный семинар, WG 2006, Берген, Норвегия, 22-24 июня 2006 г., исправленные статьи (PDF), Конспект лекций по информатике, 4271, Берлин: Springer, стр. 325–335, Дои:10.1007/11917496_29, МИСТЕР  2290741.
  24. ^ О тотальных функциях, теоремах существования и вычислительной сложности
  25. ^ http://www.openproblemgarden.org/?q=op/theoretical_computer_science/subset_sums_equality
  26. ^ Пападимитриу, Христос Х.; Яннакакис, Михалис (1996), "Об ограниченном недетерминизме и сложности размерности V-C", Журнал компьютерных и системных наук, 53 (2, часть 1): 161–170, Дои:10.1006 / jcss.1996.0058, МИСТЕР  1418886

внешняя ссылка