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