NL (złożoność) - NL (complexity)

Nierozwiązany problem w informatyce :

(więcej nierozwiązanych problemów w informatyce)

W teorii złożoności obliczeniowej , NL ( N ondeterministic L ogarithmic przestrzeń) to klasa złożoności zawiera problemy decyzyjne , które mogą być rozstrzygnięte przez niedeterministycznych maszyny Turingowi stosując logarytmiczną ilości przestrzeni pamięci .

NL jest uogólnieniem L , klasy dla problemów przestrzeni logów na deterministycznej maszynie Turinga . Ponieważ każda deterministyczna maszyna Turinga jest również niedeterministyczną maszyną Turinga , mamy, że L jest zawarte w NL .

NL można formalnie zdefiniować w kategoriach niedeterministycznej przestrzeni zasobów obliczeniowych (lub NSPACE) jako NL = NSPACE (log n ).

Ważne wyniki w teorii złożoności pozwalają nam powiązać tę klasę złożoności z innymi klasami, mówiąc nam o względnej mocy zaangażowanych zasobów. Z drugiej strony wyniki w dziedzinie algorytmów mówią nam, jakie problemy można rozwiązać za pomocą tego zasobu. Podobnie jak w przypadku większości teorii złożoności, wiele ważnych pytań dotyczących NL wciąż pozostaje otwartych (patrz Nierozwiązane problemy w informatyce ).

Czasami NL jest określany jako RL ze względu na jego probabilistyczną definicję poniżej; jednak ta nazwa jest częściej używana w odniesieniu do randomizowanej przestrzeni logarytmicznej , która nie jest równa NL .

NL-kompletne problemy

Wiadomo, że kilka problemów jest zakończonych NL przy ograniczeniu przestrzeni dziennika , w tym łączność ST i zgodność z 2 . Łączność ST pyta, dla węzłów S i T w grafie skierowanym , czy T jest osiągalny z S . 2-satisfiability pyta, biorąc pod uwagę formułę zdaniową, w której każda klauzula jest alternatywą dwóch literałów, czy istnieje przypisanie zmiennej, które sprawia, że ​​formuła jest prawdziwa. Przykładową instancją, gdzie wskazuje nie , może być:

Zabezpieczenia

Wiadomo, że NL jest zawarte w P , ponieważ istnieje algorytm czasu wielomianowego dla spełnialności 2 , ale nie wiadomo, czy NL = P, czy L = NL . Wiadomo, że NL = co-NL , gdzie co-NL to klasa języków, których dopełnienia są w NL . Ten wynik ( twierdzenie Immermana–Szelepcsényiego ) został niezależnie odkryty przez Neila Immermana i Róberta Szelepcsényiego w 1987 roku; za tę pracę otrzymali w 1995 roku Nagrodę Gödla .

W złożoności drukowanej , NL mogą być umieszczone w NC hierarchii. W Papadimitriou 1994, Twierdzenie 16.1, mamy:

.

Dokładniej, NL jest zawarte w AC 1 . Wiadomo, że NL to ZPL , klasa problemów rozwiązywanych przez algorytmy losowe w przestrzeni logarytmicznej i czasie nieograniczonym, bez błędu. Nie wiadomo jednak ani nie uważa się, że jest równy RLP lub ZPLP , ograniczeniom czasu wielomianowego RL i ZPL , które niektórzy autorzy nazywają RL i ZPL .

Możemy odnieść NL do przestrzeni deterministycznej za pomocą twierdzenia Savitcha , które mówi nam, że każdy niedeterministyczny algorytm może być symulowany przez maszynę deterministyczną w co najwyżej kwadratowo większej przestrzeni. Z twierdzenia Savitcha wynika bezpośrednio, że:

Było to najsilniejsze deterministyczne włączenie przestrzenne znane w 1994 r. (Papadimitriou 1994 Problem 16.4.10, „Przestrzeń symetryczna”). Ponieważ na większe klasy przestrzeni nie wpływają przyrosty kwadratowe, wiadomo, że klasy niedeterministyczne i deterministyczne są równe, tak że na przykład mamy PSPACE = NPSPACE .

Alternatywne definicje

Definicja probabilistyczna

Załóżmy, że C jest klasa złożoności od problemów decyzyjnych rozwiązywalne w logarithmithic z przestrzeni probabilistycznych maszyn Turinga , które nigdy nie akceptują nieprawidłowo ale są dopuszczone do odrzucenia błędnie mniej niż 1/3 czasu; nazywa się to jednostronnym błędem . Stała 1/3 jest dowolna; wystarczy dowolny x z 0 ≤ x < 1/2.

Okazuje się, że C = NL . Zauważ, że C , w przeciwieństwie do swojego deterministycznego odpowiednika L , nie jest ograniczone do czasu wielomianu, ponieważ chociaż ma wielomianową liczbę konfiguracji, może użyć losowości, aby uciec przed nieskończoną pętlą. Jeśli ograniczymy to do czasu wielomianowego, otrzymamy klasę RL , która jest zawarta w NL , ale nie jest znana ani uważana za równą NL .

Istnieje prosty algorytm, który ustala, że C = NL . Oczywiście C jest zawarte w NL , ponieważ:

  • Jeśli ciąg nie jest w języku, oba odrzucają na wszystkich ścieżkach obliczeniowych.
  • Jeśli ciąg jest w języku, algorytm NL akceptuje co najmniej jedną ścieżkę obliczeniową, a algorytm C akceptuje co najmniej dwie trzecie swoich ścieżek obliczeniowych.

Aby pokazać, że NL jest zawarte w C , po prostu bierzemy algorytm NL i wybieramy losową ścieżkę obliczeniową o długości n i wykonujemy to 2 n razy. Ponieważ żadna ścieżka obliczeniowa nie przekracza długości n i ponieważ w sumie jest 2 n ścieżek obliczeniowych, mamy dużą szansę na trafienie akceptującej (ograniczonej poniżej stałą).

Jedynym problemem jest to, że nie mamy miejsca w logu na licznik binarny, który osiąga 2n . Aby obejść ten problem, zastępujemy go losowym licznikiem, który po prostu odwraca n monet i zatrzymuje się i odrzuca, jeśli wszystkie wylądują na głowach. Ponieważ to zdarzenie ma prawdopodobieństwo 2 − n , spodziewamy się , że przed zatrzymaniem wykonamy średnio 2 n kroków. Musi tylko zachować bieżącą całkowitą liczbę głowic w rzędzie, które widzi, którą może policzyć w obszarze dziennika.

Ze względu na twierdzenie Immermana–Szelepcsényiego , zgodnie z którym NL jest domknięte pod uzupełnieniami, jednostronny błąd w tych obliczeniach probabilistycznych można zastąpić błędem zerowym. Oznacza to, że problemy te można rozwiązać za pomocą probabilistycznych maszyn Turinga, które używają przestrzeni logarytmicznej i nigdy nie popełniają błędów. Odpowiednia klasa złożoności, która również wymaga, aby maszyna używała tylko czasu wielomianowego, nazywa się ZPLP .

Tak więc, gdy patrzymy tylko na samą przestrzeń, wydaje się, że randomizacja i niedeterminizm są równie potężne.

Definicja certyfikatu

NL można równoważnie scharakteryzować certyfikatami , analogicznie do klas takich jak NP . Rozważmy deterministyczną maszynę Turinga ograniczoną przestrzenią logarytmiczną, która ma dodatkową taśmę wejściową tylko do odczytu i tylko do odczytu. Język jest w NL wtedy i tylko wtedy, gdy taka maszyna Turinga przyjmie dowolne słowo w języku dla odpowiedniego wyboru certyfikatu na dodatkowej taśmie wejściowej i odrzuci każde słowo, które nie jest w języku, niezależnie od certyfikatu.

Cem Say i Abuzer Yakaryılmaz udowodnili, że deterministyczną maszynę Turinga w przestrzeni logarytmicznej w powyższym stwierdzeniu można zastąpić probabilistyczną maszyną Turinga o stałej przestrzeni z błędem ograniczonym, która może używać tylko stałej liczby losowych bitów.

Opisowa złożoność

Istnieje prosta logiczna charakterystyka języka NL : zawiera dokładnie te języki, które można wyrazić w logice pierwszego rzędu z dodanym operatorem domknięcia przechodniego .

Właściwości zamknięcia

Klasa NL jest zamknięta pod operacjami komplementacja, suma, a zatem przecięcie, konkatenacja i gwiazda Kleene .

Uwagi

Bibliografia