ZPP (složitost)
Třída ZPP je předmětem teorie složitosti v teoretické informatice . Je to třída rozhodovacích problémů na pravděpodobnostním Turingově stroji . Zkratka ZPP pochází z pravděpodobnostního polynomiálního času s nulovou chybou .
Definice
Existuje několik ekvivalentních definic ZPP. Začneme tím, který mu dá jméno.
Definice podle očekávaného polynomiálního času
Třída ZPP je sada problémů nebo ekvivalentních jazyků , pro které existuje pravděpodobnostní Turingův stroj, jako například:
- Stroj se nemýlí: odmítá slova, která nejsou v jazyce, a přijímá ta, která do něj patří (jako u třídy bez pravděpodobnosti).
- Čas výpočtu je polynomiální v očekávání .
Definice s odpovědí „Nevím“
ZPP je třída problémů, které lze vyřešit na pravděpodobnostním polynomiálním Turingově stroji s následujícími vlastnostmi:
- Odpoví Ano, Ne nebo Nevím.
- Pokud je odpověď Ano, pak je slovo v jazyce, pokud není, není.
- Odpovídá Nevím s pravděpodobností menší nebo rovnou 1/2.
Definice průnikem
Třída ZPP je také průsečíkem tříd RP a co-RP :
Vztahy s ostatními třídami
Podle definice: .
A také máme: P .
Problémy v ZPP
Dějiny
Tuto třídu představil J. Gill v článku Výpočetní složitost pravděpodobnostních Turingových strojů , současně s třídou RP .
Bibliografie
(en) Sanjeev Arora a Boaz Barak , Výpočetní složitost: moderní přístup , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , kap. 7
Externí odkaz
Poznámky a odkazy
- Složitost Zoo
- (in) John Gill , „ Výpočetní složitost pravděpodobnostního Turingova stroje “ , SIAM Journal we Computing , roč. 6, n O 4, 1977, str. 675-695