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

Schemat losowych klas złożoności
ZPP w stosunku do innych probabilistycznych klas złożoności ( RP , co-RP, BPP , BQP , PP ), które uogólniają P w ramach PSPACE . Nie wiadomo, czy którekolwiek z tych ograniczeń są surowe.

W teorii złożoności , ZPP (zero błędów probabilistyczny czas wielomian ) to klasa złożoności problemów, dla których probabilistyczny maszyna Turinga istnieje z tych właściwości:

  • Zawsze zwraca poprawną odpowiedź TAK lub NIE.
  • Czas działania jest wielomianowy w oczekiwaniu na każde wejście.

Innymi słowy, jeśli algorytm może rzucić prawdziwie losową monetą podczas działania, zawsze zwróci poprawną odpowiedź, a dla problemu o rozmiarze n istnieje pewien wielomian p ( n ) taki, że średnia działająca czas będzie mniejszy niż p ( n ), chociaż czasami może być znacznie dłuższy. Taki algorytm nazywa się algorytmem Las Vegas .

Alternatywnie, ZPP można zdefiniować jako klasę problemów, dla których istnieje probabilistyczna maszyna Turinga o następujących właściwościach:

  • Zawsze działa w czasie wielomianowym.
  • Zwraca odpowiedź TAK, NIE lub NIE WIEM.
  • Odpowiedź zawsze brzmi albo NIE WIEM, albo jest poprawna.
  • Zwraca NIE WIEM z prawdopodobieństwem najwyżej 1/2 dla każdego wejścia (i poprawną odpowiedź w innym przypadku).

Te dwie definicje są równoważne.

Definicja ZPP jest oparta na probabilistycznych maszynach Turinga, ale dla jasności należy zauważyć, że inne klasy złożoności na nich oparte obejmują BPP i RP . Klasa BQP jest oparta na innej maszynie z losowością: komputerze kwantowym .

Definicja skrzyżowania

Klasa ZPP jest dokładnie równa przecięciu klas RP i co-RP . Często przyjmuje się, że jest to definicja ZPP . Aby to pokazać, najpierw zwróć uwagę, że każdy problem, który dotyczy zarówno RP, jak i co-RP, ma następujący algorytm Las Vegas :

  • Załóżmy, że mamy język L rozpoznawany zarówno przez algorytm RP A, jak i (prawdopodobnie zupełnie inny) algorytm co-RP B.
  • Mając dane wejściowe, uruchom A na wejściu przez jeden krok. Jeśli zwróci TAK, odpowiedź musi brzmieć TAK. W przeciwnym razie uruchom B na wejściu przez jeden krok. Jeśli zwraca NIE, odpowiedź musi brzmieć NIE. Jeśli tak się nie stanie, powtórz ten krok.

Zwróć uwagę, że tylko jedna maszyna może kiedykolwiek udzielić złej odpowiedzi, a prawdopodobieństwo, że ta maszyna poda złą odpowiedź podczas każdego powtórzenia, wynosi co najwyżej 50%. Oznacza to, że szansa na dotarcie do k- tej rundy maleje wykładniczo w k , pokazując, że oczekiwany czas przebiegu jest wielomianowy. To pokazuje, że RP przecinają się co-RP jest zawarte w ZPP .

Aby pokazać, że ZPP jest zawarty w RP przecinają się co-RP , załóżmy, że mamy algorytm C z Las Vegas do rozwiązania problemu. Następnie możemy skonstruować następujący algorytm RP :

  • Uruchom C przez co najmniej dwukrotność oczekiwanego czasu działania. Jeśli daje odpowiedź, podaj tę odpowiedź. Jeśli nie daje żadnej odpowiedzi, zanim ją zatrzymamy, odpowiedz NIE.

Według nierówności Markowa , szansa, że ​​da odpowiedź, zanim ją zatrzymamy, wynosi co najmniej 1/2. Oznacza to, że szansa, że ​​udzielimy złej odpowiedzi w przypadku TAK, zatrzymując się i dając NIE, wynosi co najwyżej 1/2, co pasuje do definicji algorytmu RP . Współ-RP algorytm jest identyczny, oprócz tego, że daje TAK Jeśli C „razy out”.

Świadek i dowód

O klasach NP , RP i ZPP można myśleć w kategoriach dowodu przynależności do zbioru.

Definicja: weryfikator V dla zbioru X jest maszyną Turinga takie, że:

  • jeśli x jest w X, to istnieje łańcuch w taki, że V ( x , w ) akceptuje;
  • jeśli x nie jest w X , to dla wszystkich łańcuchów w , V ( x , w ) odrzuca.

Ciąg w można traktować jako dowód przynależności. W przypadku krótkich dowodów (o długości ograniczonej wielomianem wielkości danych wejściowych), które można skutecznie zweryfikować ( V jest deterministyczną maszyną Turinga w czasie wielomianu), ciąg w nazywany jest świadkiem .

Uwagi:

  • Definicja jest bardzo asymetryczna. Dowodem na to, że x jest w X, jest pojedynczy ciąg. Dowodem na to, że x nie jest w X, jest zbiór wszystkich ciągów, z których żaden nie jest dowodem przynależności.
  • Dostępność świadka jest jednolita. Dla wszystkich x w X musi być świadek. Nie jest tak, gdy pewne x w X są zbyt trudne do zweryfikowania, podczas gdy większość nie.
  • Świadek nie musi być tradycyjnie interpretowanym dowodem. Jeśli V jest probabilistyczną maszyną Turinga, która mogłaby prawdopodobnie zaakceptować x, jeśli x jest w X, to dowodem jest ciąg rzutów monetą, który prowadzi maszynę, przez szczęście, intuicję lub geniusz, do zaakceptowania x .
  • Współkoncepcja jest dowodem braku członkostwa lub członkostwa w zbiorze uzupełniającym.

Klasy NP , RP i ZPP to zestawy, które mają świadków członkostwa. Klasa NP wymaga tylko istnienia świadków. Mogą być bardzo rzadkie. Z 2 f (| x |) możliwych ciągów, z f wielomianem, tylko jeden musi spowodować akceptację weryfikatora (jeśli x jest w X. Jeśli x nie jest w X, żaden łańcuch nie spowoduje, że weryfikator zaakceptuje).

W przypadku klas RP i ZPP świadkiem będzie prawdopodobnie dowolny wybrany losowo ciąg.

Odpowiednie współklasy mają świadectwo o braku członkostwa. W szczególności co-RP jest klasą zbiorów, dla których, jeśli x nie jest w X, dowolny losowo wybrany ciąg prawdopodobnie będzie świadkiem braku członkostwa. ZPP to klasa zbiorów, dla których dowolny losowy ciąg prawdopodobnie będzie świadkiem x w X lub x nie w X, niezależnie od przypadku.

Połączenie tej definicji z innymi definicjami RP , co-RP i ZPP jest łatwe. Probabilistyczna maszyna Turinga w czasie wielomianu V * w ( x ) odpowiada deterministycznej maszynie Turinga w czasie wielomianu V ( x , w ) poprzez zastąpienie losowej taśmy V * drugą taśmą wejściową dla V, na której zapisana jest sekwencja rzut monetą. Wybierając świadka jako losowy ciąg, weryfikator jest probabilistyczną Wielomianową Maszyną Turinga, której prawdopodobieństwo przyjęcia x, gdy x jest w X, jest duże (powiedzmy większe niż 1/2), ale zero, jeśli x X (dla RP ); odrzucenia x, gdy x nie jest w X jest duże, ale zero, jeśli x X (dla co-RP ); i poprawnego przyjęcia lub odrzucenia x jako członka X jest duże, ale zero nieprawidłowego przyjęcia lub odrzucenia x (dla ZPP ).

Dzięki wielokrotnemu losowemu wyborowi potencjalnego świadka duże prawdopodobieństwo, że losowy ciąg jest świadkiem, daje oczekiwany algorytm czasu wielomianowego do akceptowania lub odrzucania danych wejściowych. I odwrotnie, jeśli oczekiwany jest czas wielomianu maszyny Turinga (dla dowolnego podanego x), to znaczna część przebiegów musi być ograniczona wielomianem, a sekwencja monet użyta w takim przebiegu będzie świadkiem.

ZPP należy skontrastować z BPP . Klasa BPP nie wymaga świadków, chociaż świadkowie są wystarczający (stąd BPP zawiera RP , co-RP i ZPP ). BPP język ma V (x, w) przyjąć na (jasny) w większości łańcuchów jeśli x jest w X i odwrotnie odrzucić na (jasny) w większości łańcuchów jeśli x nie jest w X . Żadna pojedyncza struna nie musi być ostateczna, a zatem nie można ich na ogół uważać za dowody lub świadków.

Teoretyczne właściwości złożoności

Wiadomo, że ZPP jest zamykany pod uzupełnianiem; to znaczy ZPP = co-ZPP.

ZPP jest sam w sobie niski , co oznacza, że ​​maszyna ZPP z mocą do natychmiastowego rozwiązywania problemów ZPP (maszyna ZPP-wyrocznia) nie jest tak potężna, jak maszyna bez tej dodatkowej mocy. W symbolach ZPP ZPP = ZPP .

ZPP NP BPP = ZPP NP .

NP BPP jest zawarty w ZPP NP .

Połączenie z innymi klasami

Ponieważ ZPP = RP coRP , ZPP jest oczywiście zawarty zarówno w RP, jak i coRP .

Klasa P jest zawarta w ZPP , a niektórzy informatycy przypuszczali, że P = ZPP , tj. Każdy algorytm Las Vegas ma deterministyczny odpowiednik wielomianu w czasie.

Istnieje wyrocznia, w stosunku do której ZPP = EXPTIME . Dowód na ZPP = EXPTIME sugerowałby, że P ZPP , jako P EXPTIME (patrz twierdzenie o hierarchii czasu ).

Zobacz też

Linki zewnętrzne