Wykres konfiguracji

Grafy konfiguracyjne są narzędziem teoretycznym używanym w teorii złożoności obliczeniowej do udowodnienia związku między osiągalnością grafów a klasami złożoności . ^{[ potrzebne źródło ]}

Definicja

Teoretyczny model obliczeniowy, taki jak maszyna Turinga lub automaty skończone , wyjaśnia, jak wykonać obliczenia. Model wyjaśnia, czym jest początkowa konfiguracja maszyny i jakie kroki należy podjąć, aby kontynuować obliczenia, aż w końcu się zatrzymamy. Konfiguracja , zwana także Opisem Chwilowym (ID), jest skończoną reprezentacją maszyny w danym czasie. Np. dla automatu skończonego i zadanego wejścia konfiguracją będzie aktualny stan i liczba odczytanych liter, dla maszyny Turinga będzie to stan, zawartość taśmy i pozycja głowicy. Graf konfiguracyjny jest skierowanym grafem etykietowanym , w którym etykietą wierzchołków są możliwe konfiguracje modeli i gdzie istnieje krawędź od jednej konfiguracji do drugiej, jeśli odpowiada ona krokowi obliczeniowemu modelu. ^{[ potrzebne źródło ]}

Początkowa i akceptująca konfiguracja maszyny to specjalne wierzchołki grafu konfiguracji. Obliczenie akceptuje wtedy i tylko wtedy, gdy istnieje ścieżka od wierzchołka początkowego do wierzchołka akceptującego.

Przydatna właściwość

Jeśli istnieje dokładnie jeden stan początkowy, to obliczenia są deterministyczne wtedy i tylko wtedy, gdy z dowolnej konfiguracji istnieje co najwyżej jeden możliwy krok, więc wtedy i tylko wtedy, gdy wykres ma stopień zewnętrzny 1. [ ^{Potrzebne źródło ]}

Po dodaniu fikcyjnego wierzchołka początkowego z krawędzią do każdego wierzchołka początkowego i fikcyjnego wierzchołka akceptującego z krawędzią z każdego wierzchołka akceptującego sprawdzenie, czy istnieje obliczenie akceptujące, wymaga jedynie sprawdzenia, czy istnieje ścieżka od wierzchołka początkowego do akceptującego wierzchołek, czyli problem osiągalności .

Mówimy, że obliczenie jest jednoznaczne, jeśli istnieje co najwyżej jedna ścieżka od wierzchołka początkowego do wierzchołka akceptującego.

Cykl na wykresie odpowiada nieskończonej pętli w obliczeniach.

Rozmiar wykresu

Wykres obliczeniowy może mieć nieskończony rozmiar, jeśli nie ma ograniczeń co do możliwych konfiguracji; w istocie łatwo zauważyć, że istnieją maszyny Turinga, które mogą osiągać dowolnie duże konfiguracje.

$również$ posiadanie grafów skończonych: w deterministycznym automacie $skończonym$ ze , dla danego słowa o rozmiarze składa się z położenia głowy i aktualnego stanu. Tak więc wykres ma rozmiar $($ $) s}$ , a dostępna część ze stanu początkowego ma rozmiar .

Korzystanie z tego obiektu

Pojęcie to jest przydatne, ponieważ redukuje problemy obliczeniowe do problemów z osiągalnością grafów .

Na przykład, ponieważ osiągalność jest w NL , kiedy możemy reprezentować konfiguracje w przestrzeni, która jest logarytmiczna pod względem rozmiaru danych wejściowych, i ponieważ konfiguracja Maszyny Turinga w NL jest rzeczywiście logarytmiczna, wynika z tego, że osiągalność grafu jest kompletna dla NL.

Z drugiej strony pomaga zweryfikować złożoność modelu obliczeniowego; problem decyzyjny dla (deterministycznego) modelu, którego konfiguracje są w przestrzeni logarytmicznej wielkości wejściowej, jest w ( L ) NL . Tak jest na przykład w przypadku automatów skończonych i automatów skończonych z jednym licznikiem.

Bibliografia

Arora, Sanjeev ; Barak, Boaz (2009). Złożoność obliczeniowa, nowoczesne podejście . Wydawnictwo Uniwersytetu Cambridge . ISBN 978-0-521-42426-4 . Sekcja 4.3: Kompletność NL, s. 87.