ZPP (complejidad)
La clase ZPP , es un objeto de teoría de la complejidad , en informática teórica . Es una clase de problemas de decisión en la máquina probabilística de Turing . El acrónimo ZPP proviene de Zero-Error Probabilistic Polynomial time .
Definiciones
Hay varias definiciones equivalentes de ZPP. Empezamos por el que le da nombre.
Definición por el tiempo polinomial esperado
La clase ZPP es el conjunto de problemas, o lenguajes equivalentes , para los que existe una máquina de Turing probabilística como:
- La máquina no se equivoca: rechaza las palabras que no están en el lenguaje y acepta las que le pertenecen (como en una clase no probabilística).
- El tiempo de cálculo es polinómica en expectativa .
Definiciones con la respuesta "No sé"
ZPP es la clase de problemas que se pueden resolver en una máquina de Turing de tiempo polinomial probabilístico que tiene las siguientes propiedades:
- Ella responde Sí, No o No sé.
- Si la respuesta es Sí, entonces la palabra está en el idioma, si es No, no lo está.
- Responde No sé con una probabilidad menor o igual a 1/2.
Definición por intersección
La clase ZPP es también la intersección de las clases RP y co-RP :
Relaciones con otras clases
Por definición: .
Y también tenemos: P .
Problemas en ZPP
Historia
Esta clase fue introducida por J. Gill en el artículo Complejidad computacional de las máquinas probabilísticas de Turing , al mismo tiempo que la clase RP .
Bibliografía
(en) Sanjeev Arora y Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , cap. 7
Enlace externo
Notas y referencias
- Complexity Zoo
- (en) John Gill , " Complejidad computacional de la máquina probabilística de Turing " , SIAM Journal we Computing , vol. 6, n o 4, 1977, p. 675-695