НП-средний - NP-intermediate
По вычислительной сложности задачи, которые относятся к классу сложности NP, но не принадлежат ни к классу P, ни к NP-полным , называются NP-промежуточными , а класс таких задач называется NPI . Теорема Ладнера , показанная в 1975 году Ричардом Э. Ладнером , является результатом утверждения, что если P ≠ NP , то NPI не пусто; то есть NP содержит проблемы, которые не являются ни P, ни NP-полными. Так как также верно, что если существуют проблемы NPI, то P ≠ NP, отсюда следует, что P = NP тогда и только тогда, когда NPI пусто.
В предположении, что P ≠ NP, Ладнер явно конструирует проблему в NPI, хотя эта задача является искусственной и в остальном неинтересна. Остается открытым вопрос, обладает ли какая-либо «естественная» проблема таким же свойством: теорема Шефера о дихотомии предоставляет условия, при которых классы задач с ограниченной булевой выполнимостью не могут находиться в NPI. Некоторые проблемы, которые считаются хорошими кандидатами на то, чтобы быть NP-промежуточными, - это проблема изоморфизма графов , факторизация и вычисление дискретного логарифма .
Список проблем, которые могут быть NP-промежуточными
Алгебра и теория чисел
- Факторинг целых чисел
- Проблема дискретного журнала и другие, связанные с криптографическими предположениями
- Проблемы изоморфизма: проблема группового изоморфизма , групповой автоморфизм , кольцевой изоморфизм , кольцевой автоморфизм
- Цифры в ящиках задачи
- Проблема линейной делимости
Логическая логика
- Пересекающийся монотонный SAT
- Проблема минимального размера цепи
- Монотонная самодвойственность
Вычислительная геометрия и вычислительная топология
- Вычисление расстояния вращения между двумя бинарными деревьями или расстояния отражения между двумя триангуляциями одного и того же выпуклого многоугольника
- Задача на магистрали восстановления точек на линии по их мультимножеству расстояний
- Проблема раскроя с постоянным количеством длин объекта
- Узел мелочь
- Решение, является ли данное триангулированное 3-многообразие 3-сферой
- Разрывная версия ближайшего вектора в решеточной задаче
- Нахождение простой замкнутой квазигеодезической на выпуклом многограннике
Теория игры
- Определение победителя в паритетных играх
- Определение того, у кого больше шансов на победу в стохастической игре
- Контроль повестки дня для сбалансированных турниров с выбыванием одного игрока
Алгоритмы графа
- Проблема изоморфизма графов
- Плоское минимальное деление пополам
- Решение, допускает ли граф изящную разметку
- Признавая листовое полномочие и K -leaf полномочия
- Распознавание графов ограниченной ширины клики
- Поиск одновременного вложения с фиксированными краями
Разное
- Предполагая, что NEXP не равен EXP , дополненные версии проблем NEXP-complete
- Проблемы в TFNP
- Сумма подмножества голубятни
- Нахождение размера VC
использованная литература
внешние ссылки
- Зоопарк сложности : класс NPI
- Базовая структура, восстанавливаемость по Тьюрингу и NP-твердость
- Лэнс Фортноу (24 марта 2003 г.). «Основы сложности, Урок 16: Теорема Ладнера» . Проверено 1 ноября 2013 года .