Промежуточность - это алгоритмическая проблема в теории порядка об упорядочении набора элементов с учетом ограничений, заключающихся в том, что одни элементы должны быть размещены между другими. [1] Он имеет приложения в биоинформатике [2] и был показан Опатриным (1979) как NP - полный . [3]
Входными данными для проблемы промежуточности является набор упорядоченных троек элементов. Элементы, перечисленные в этих тройках, должны быть размещены в общем порядке с тем свойством, что для каждой из заданных троек средний элемент в тройке появляется в выводе где-то между двумя другими элементами. Элементы каждой тройки не обязательно должны быть последовательными в выводе. [1] [3]
В первом из этих порядков вывода для всех пяти входных троек средний элемент тройки появляется между двумя другими элементами. Однако для второго порядка вывода элемент 4 не находится между элементами 1 и 2, что противоречит заданному требованию. тройкой (2,4,1).
Если входные данные содержат две тройки, такие как (1,2,3) и (2,3,1) с одними и теми же тремя элементами, но с другим выбором среднего элемента, то допустимого решения нет. Однако существуют более сложные способы формирования набора троек без правильного решения, не содержащего такой пары противоречивых троек.
Opatrný (1979) показал, что версия решения проблемы промежуточности (в которой алгоритм должен решить, существует ли действительное решение) является NP-полной двумя способами: за счет редукции от 3-выполнимости , а также за счет другой редукции. из 2-раскраски гиперграфа . [3] Однако ее можно легко решить, если все неупорядоченные тройки элементов представлены упорядоченной тройкой входных данных, выбрав один из двух элементов, которые не находятся между другими, в качестве начала упорядочения, а затем используя тройки, включающие этот элемент, чтобы сравнить относительные позиции каждой пары оставшихся элементов.
Связанная с этим проблема нахождения упорядочения, которое максимизирует количество удовлетворенных троек, является MAXSNP-трудной , подразумевая, что невозможно достичь отношения аппроксимации, сколь угодно близкого к 1, за полиномиальное время , если только P = NP . [1] Трудно решить или аппроксимировать даже для плотных экземпляров, которые включают упорядоченную тройку для каждой возможной неупорядоченной тройки элементов. [4] Доказано, что минимальная версия задачи, ограниченная турнирами, имеет полиномиальные схемы аппроксимации времени (PTAS). [5]Можно достичь коэффициента аппроксимации 1/3 (в ожидании), упорядочив элементы случайным образом, и эта простая стратегия дает наилучшее возможное приближение за полиномиальное время, если гипотеза об уникальных играх верна. [6] Также можно использовать полуопределенное программирование или комбинаторные методы, чтобы найти порядок, который удовлетворяет по крайней мере половине троек любого удовлетворяющего экземпляра, за полиномиальное время. [1] [7]