łączność st

W informatyce st-connectivity lub STCON to problem decyzyjny polegający na pytaniu o wierzchołki s i t w grafie skierowanym , czy t jest osiągalne z s .

Formalnie problem decyzyjny jest dany przez

ŚCIEŻKA = { ⟨ re , s , t ⟩ | D jest grafem skierowanym ze ścieżką od wierzchołka s do t } .

Złożoność

Na komputerze sekwencyjnym łączność st można łatwo rozwiązać w czasie liniowym albo przez przeszukiwanie w głąb , albo przeszukiwanie wszerz . Zainteresowanie tym problemem złożoności obliczeniowej dotyczy jej złożoności w odniesieniu do bardziej ograniczonych form obliczeń. Na przykład klasa złożoności problemów, które mogą być rozwiązane przez niedeterministyczną maszynę Turinga przy użyciu tylko logarytmicznej ilości pamięci, nazywa się NL . Można pokazać, że problem st-łączności występuje w NL, ponieważ niedeterministyczna maszyna Turinga może odgadnąć następny węzeł ścieżki, podczas gdy jedyną informacją, która musi być przechowywana, jest całkowita długość ścieżki i który węzeł jest aktualnie rozważany. Algorytm kończy się, gdy osiągnięty zostanie węzeł docelowy t lub długość dotychczasowej ścieżki przekroczy n , czyli liczbę węzłów na grafie.

Dopełnienie st-łączności , znane jako st-non-łączności , jest również w klasie NL, ponieważ NL = coNL przez twierdzenie Immermana-Szelepcsényi'ego .

W szczególności problem st-connectivity jest w rzeczywistości NL-complete , to znaczy każdy problem w klasie NL można zredukować do łączności w ramach redukcji przestrzeni logarytmicznej . Pozostaje to prawdą dla silniejszego przypadku redukcji pierwszego rzędu ( Immerman 1999 , P. 51). Redukcja przestrzeni logarytmicznej z dowolnego języka w NL do STCON przebiega w następujący sposób: Rozważmy niedeterministyczną przestrzeń logarytmiczną Turinga M, która akceptuje język w NL. Ponieważ na taśmie roboczej jest tylko przestrzeń logarytmiczna, wszystkie możliwe stany maszyny Turinga (gdzie stan jest stanem wewnętrznej maszyny skończonej, pozycją głowicy i zawartością taśmy roboczej) są wielomianowe. Odwzoruj wszystkie możliwe stany deterministycznej maszyny logarytmicznej na wierzchołki grafu i umieść krawędź między u i v, jeśli stan v można osiągnąć z u w obrębie jednego kroku maszyny niedeterministycznej. Teraz problem, czy maszyna akceptuje, jest taki sam, jak problem, czy istnieje ścieżka od stanu początkowego do stanu akceptującego.

  Twierdzenie Savitcha gwarantuje, że algorytm może być symulowany w przestrzeni deterministycznej O (log ² n ).

Ten sam problem dla grafów nieskierowanych nazywany jest nieskierowaną łącznością st i został pokazany jako L -zupełny przez Omera Reingolda . Badania te przyniosły mu nagrodę Grace Murray Hopper w 2005 roku . Wcześniej wiadomo było, że nieskierowana spójność st jest zupełna dla klasy SL , więc praca Reingolda pokazała, że ​​SL jest tą samą klasą co L. Na przemiennych grafach problem jest P -zupełny ( Immerman 1999 , s. 54).

•   Sipser, Michael (2006), Wprowadzenie do teorii obliczeń , Thompson Course Technology, ISBN 0-534-95097-3
•   Immerman, Neil (1999), Złożoność opisowa , Nowy Jork: Springer-Verlag, ISBN 0-387-98600-6