ZPP osztály

A számítási komplexitás elméletében a ZPP ( angol. zero-error probabilistic polynomial time - error-free probabilistic polynomial ) az „Igen” vagy „Nem” választ tartalmazó problémák osztálya, amelyre létezik egy valószínűségi Turing-gép , amely kielégíti a következő tulajdonságokkal:

• Mindig helyesen válaszol "Igen" vagy "Nem".
• Egy adott Turing-gép futási idejére vonatkozó matematikai elvárás polinomiális (maga a futási idő végtelenül nagy lehet).

Van egy alternatív tulajdonságkészlet:

• A Turing-gép mindig polinomiális időben fut.
• Válaszol „Igen”, „Nem” vagy „Nem tudom”.
• A válasz lehet helyes vagy "nem tudom".
• Ha a helyes válasz „Igen”, a Turing-gép legalább ½ valószínűséggel „Igen”-t válaszol.
• Ha a helyes válasz „Nem”, akkor a Turing-gép legalább ½ valószínűséggel „Nem”-t válaszol.

A két tulajdonságkészlet egyikének kiválasztása egyenértékű ZPP osztálydefiníciókat eredményez. Az ezeket a tulajdonságokat kielégítő Turing-gépet néha Las Vegas-i típusú Turing-gépnek is nevezik .

Egyenértékű definíció a metszéspont szempontjából

A ZPP osztály megegyezik az RP és a Co-RP osztályok metszéspontjával . Ezt gyakran a ZPP definíciójának tekintik . Ennek demonstrálására vegye figyelembe, hogy minden olyan probléma, amely mind az RP -hez, mind a társRP - hez tartozik, Las Vegas típusú algoritmussal rendelkezik :

• Tegyük fel, hogy létezik egy L nyelv, amelyet egy RP -algoritmus A felismer, és egy (esetleg A -tól eltérő ) társRP - algoritmus B .
• Végezzük el az A algoritmus egy lépését a bemeneti sorozaton. Ha "Igen"-t ad vissza, akkor a végső válasznak "Igen"-nek kell lennie. Ellenkező esetben futtassa a B algoritmus egy lépését ugyanazzal a bemenettel. Ha „Nem”-et válaszol, akkor a végső válasz „Nem” lesz. Ha az előző feltételek egyike sem teljesül, ismételje meg ezt a lépést.

Vegye figyelembe, hogy az A vagy B algoritmusok közül csak az egyik tud helytelen választ adni, és ennek az eseménynek a valószínűsége minden lépésben 50%. Így a k -edik lépés elérésének valószínűsége k -hoz képest exponenciálisan csökken . Ez azt mutatja, hogy a várható futási idő polinom. Az elmondottakból következik, hogy az RP és a co-RP osztályok metszéspontját a ZPP tartalmazza .

Mutassuk meg, hogy a ZPP az RP és a co-RP metszéspontjában található . Legyen egy Las Vegas-i típusú Turing-gép C , ami megoldja a problémát. Jelöljük a működési idejére vonatkozó matematikai elvárást M -vel (feltétel szerint véges). Ezután a következő RP algoritmust állíthatjuk össze:

• Futtassuk a C -t legalább 2M ideig . Ha ez idő alatt C választ kapott, visszaküldjük. Ha a megálló előtt nem érkezik válasz, „Nem”-et mondunk.

Annak a valószínűsége, hogy a válasz a megállás pillanata előtt megérkezik, egyenlő ½ ( Markov-egyenlőtlenségből ). Ez viszont azt jelenti, hogy annak a valószínűsége, hogy „Nem”-t válaszolunk a helyes „Igen” válaszra (ez megtörténhet a C idő előtti leállása miatt ), ½, ami kielégíti az RP definícióját . A ZPP társRP - be való beépülésének bizonyítására vagy ugyanazt az érvelést használhatjuk, vagy megfigyelhetjük, hogy a ZPP a komplement felvétele során zárt .

Irodalom

• J. Gill. Valószínűségi Turing-gépek számítási összetettsége  //  A hatodik éves ACM szimpózium a számításelméletről (STOC '74) anyaga. - New York, NY, USA: Association for Computing Machinery, 1974. - P. 91–95 . - doi : 10.1145/800119.803889 .