ZPP (złożoność) - ZPP (complexity)
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 ).