Między

Pośredniość to algorytmiczny problem w teorii porządku dotyczący porządkowania zbioru przedmiotów z zastrzeżeniem ograniczeń, zgodnie z którymi niektóre elementy muszą być umieszczone między innymi. Ma zastosowanie w bioinformatyce , a Opatrný (1979) wykazał, że jest NP -zupełny .

Oświadczenie o problemie

Dane wejściowe do problemu pośredniego to zbiór uporządkowanych trójek elementów. Pozycje wymienione w tych trójkach należy umieścić w porządku całkowitym , z tą właściwością, że dla każdej z podanych trójek środkowy element w trójce pojawia się na wyjściu gdzieś pomiędzy dwoma pozostałymi elementami. Elementy każdej trójki nie muszą być kolejne na wyjściu.

Przykłady

Na przykład kolekcja danych wejściowych potroi się

(2,1,3), (3,4,5), (1,4,5), (2,4,1), (5,2,3)

jest spełniony przez uporządkowanie wyjścia

3, 1, 4, 2, 5

ale nie przez

3, 1, 2, 4, 5.

W pierwszym z tych porządków wyjściowych, dla wszystkich pięciu trójek wejściowych, środkowa pozycja trójki pojawia się pomiędzy dwoma pozostałymi pozycjami Jednak w przypadku drugiego uporządkowania wyjściowego, pozycja 4 nie znajduje się pomiędzy pozycjami 1 i 2, co jest sprzeczne z podanym wymaganiem przez potrójne (2,4,1).

Jeśli dane wejściowe zawierają dwie trójki, takie jak (1,2,3) i (2,3,1) z tymi samymi trzema pozycjami, ale innym wyborem środkowego elementu, to nie ma prawidłowego rozwiązania. Istnieją jednak bardziej skomplikowane sposoby tworzenia zbioru trójek bez ważnego rozwiązania, które nie zawierają takiej pary sprzecznych trójek.

Złożoność

Opatrný (1979) wykazał, że wersja decyzyjna problemu pośredniego (w którym algorytm musi zdecydować, czy istnieje prawidłowe rozwiązanie) jest NP-zupełna na dwa sposoby, poprzez redukcję z 3-spełnialności , a także przez inną redukcję z hipergrafu 2-kolorowanie . Można to jednak łatwo rozwiązać, gdy wszystkie nieuporządkowane trójki elementów są reprezentowane przez uporządkowaną trójkę danych wejściowych, wybierając jedną z dwóch pozycji, które nie znajdują się między żadnymi innymi, jako początek porządkowania, a następnie używając trójek obejmujących to element, aby porównać względne pozycje każdej pary pozostałych elementów.

Powiązany problem znalezienia uporządkowania, które maksymalizuje liczbę spełnionych trójek, jest MAXSNP-trudny , co oznacza, że niemożliwe jest osiągnięcie współczynnika aproksymacji dowolnie bliskiego 1 w czasie wielomianowym , chyba że P = NP . Pozostaje trudny do rozwiązania lub przybliżenia nawet w przypadku gęstych przypadków, które obejmują uporządkowaną trójkę dla każdej możliwej nieuporządkowanej trójki elementów. Udowodniono, że minimalna wersja problemu ograniczona do turniejów ma wielomianowe schematy aproksymacji czasu (PTAS). Można osiągnąć współczynnik przybliżenia 1/3 (w oczekiwaniu), zamawiając elementy losowo, a ta prosta strategia daje najlepsze możliwe przybliżenie w czasie wielomianowym, jeśli przypuszczenie o unikalnych grach jest prawdziwe. Możliwe jest również użycie programowania półokreślonego lub metod kombinatorycznych, aby znaleźć uporządkowanie, które spełnia co najmniej połowę trójek dowolnej spełnialnej instancji w czasie wielomianowym.

W sparametryzowanej złożoności problem spełnienia jak największej liczby ograniczeń ze zbioru C ograniczeń jest wykonalny ze stałymi parametrami , gdy jest sparametryzowany przez różnicę q - | C |/3 między jakością rozwiązania q znalezioną przez sparametryzowany algorytm a | Jakość C |/3 gwarantowana w oczekiwaniu przez losowe zamówienie.

Chociaż nie ma gwarancji powodzenia, zachłanna heurystyka może znaleźć rozwiązania wielu przypadków problemu międzypośrednictwa pojawiającego się w praktyce.

Aplikacje

Jedno z zastosowań pośrednictwa pojawia się w bioinformatyce jako część procesu mapowania genów . Niektóre rodzaje eksperymentów genetycznych mogą być wykorzystane do określenia kolejności potrójnych markerów genetycznych, ale nie odróżniają sekwencji genetycznej od jej odwrócenia, więc informacje uzyskane z takiego eksperymentu określają tylko, który z trzech markerów jest środkowym. Problem pokrewieństwa jest abstrakcją problemu składania zbioru markerów w pojedynczą sekwencję przy danych eksperymentalnych tego typu.

Problem pośredniości został również wykorzystany do modelowania teorii prawdopodobieństwa , przyczynowości i czasu .