NP-intermediate
редактировать
Класс сложности задач, решаемых за недетерминированное полиномиальное время которые не являются ни полиномиальным временем, ни NP-полными
В вычислительной сложности проблемы, которые относятся к классу сложности NP, но не относятся к классу P и NP-Complete называются NP-intermediate, а класс таких задач называется NPI . Теорема Ладнера, показанная в 1975 году Ричардом Э. Ладнером, является результатом утверждения, что если P ≠ NP, то NPI не пусто; то есть NP содержит проблемы, которые не являются ни P, ни NP-полными. Так как также верно, что если проблемы NPI существуют, то P ≠ NP, то P = NP тогда и только тогда, когда NPI пусто.
В предположении, что P ≠ NP, Ладнер явно конструирует проблему в NPI, хотя эта проблема является искусственной и неинтересной. Остается открытым вопрос, обладает ли какая-либо «естественная» проблема таким же свойством: теорема Шефера о дихотомии предоставляет условия, при которых классы задач с ограниченной булевой выполнимостью не могут быть в NPI. Некоторые проблемы, которые считаются хорошими кандидатами на роль NP-промежуточного уровня: проблема изоморфизма графов, факторизация и вычисление дискретного логарифма.
Содержание
- 1 Список проблемы, которые могут быть NP-промежуточными
- 1.1 Алгебра и теория чисел
- 1.2 Логическая логика
- 1.3 Вычислительная геометрия и вычислительная топология
- 1.4 Теория игр
- 1.5 Графические алгоритмы
- 1.6 Разное
- 2 Ссылки
- 3 Внешние ссылки
Список проблем, которые могут быть NP-промежуточными
Алгебра и теория чисел
Логическая логика
- Пересекающиеся монотонные SAT
- Проблема минимального размера схемы
- Монотонная самодуальность
Вычислительная геометрия и вычисления условная топология
- Вычисление расстояния поворота между двумя бинарными деревьями или расстояния отражения между двумя триангуляциями одного и того же выпуклого многоугольника
- Задача магистрали восстановления точек на линии от их расстояния мультимножество
- Задача резки материала с постоянным числом длин объектов
- Тривиальность узла
- Определение того, является ли данное триангулированное 3-многообразие является 3-сферой
- Разрывная версия ближайшего вектора в задаче решетки
- Нахождение простой замкнутой квазигеодезической на выпуклом многограннике
Теория игр
- Определение победитель в паритетных играх
- Определение, у кого больше шансов на победу в стохастической игре
- Контроль повестки дня для сбалансированных турниров с выбыванием одного игрока
Графические алгоритмы
- Проблема изоморфизма графа
- Планарность минимальное деление пополам
- Определение, допускает ли граф изящную разметку
- Распознавание листовых мощностей и k-листовых степеней
- Распознавание графов ограниченной клики -width
- Нахождение одновременного внедрения с фиксированными краями
Разное
- Предполагая, что NEXP не равно EXP, дополненные версии NEXP- полные проблемы
- Проблемы в TFNP
- Сумма подмножества Pigeonhole
- Поиск измерения VC
Ссылки
Внешние ссылки
