ZPP (złożoność)
Klasa ZPP , jest przedmiotem teorii złożoności , w teoretycznej informatyki . Jest to klasa problemów decyzyjnych na probabilistycznej maszynie Turinga . Akronim ZPP pochodzi od Zero-Error Probabilistic Wielomian time .
Definicje
Istnieje kilka równoważnych definicji ZPP. Zaczynamy od tego, który nadaje jej nazwę.
Definicja przez czas wielomianu w oczekiwaniu
Klasa ZPP to zbiór problemów lub języków równoważnych , dla których istnieje probabilistyczna maszyna Turinga, taka jak:
- Maszyna się nie myli: odrzuca słowa, których nie ma w języku i akceptuje te, które do niego należą (jak w przypadku klasy nieprobabilistycznej).
- Czas obliczeń jest wielomian w oczekiwaniu .
Definicje z odpowiedzią „Nie wiem”
ZPP to klasa problemów, które można rozwiązać na probabilistycznej maszynie Turinga z wielomianem czasu , mającej następujące właściwości:
- Odpowiada tak, nie lub nie wiem.
- Jeśli odpowiedź brzmi tak, to słowo jest w języku, jeśli nie, to nie jest.
- Odpowiada „Nie wiem” z prawdopodobieństwem mniejszym lub równym 1/2.
Definicja przez przecięcie
Klasa ZPP to także skrzyżowanie klas RP i co-RP :
Relacje z innymi klasami
Z definicji: .
A także mamy: P .
Problemy w ZPP
Historia
Klasę tę wprowadził J. Gill w artykule Złożoność obliczeniowa probabilistycznych maszyn Turinga , w tym samym czasie co klasa RP .
Bibliografia
(en) Sanjeev Arora i Boaz Barak , Złożoność obliczeniowa: nowoczesne podejście , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , rozdz. 7
Link zewnętrzny
Uwagi i odniesienia
- Zoo złożoności
- (w) John Gill , „ Złożoność obliczeniowa probabilistycznej maszyny Turinga ” , SIAM Journal we Computing , vol. 6, n O 4, 1977, s. 675-695