ZPP (complejidad)

ZPP en relación con otras clases de complejidad probabilística (RP, co-RP, BPP, BQP, PP), que generalizan P dentro de PSPACE. Se desconoce si alguna de estas contracciones es estricta.

En la teoría de la complejidad, ZPP (tiempo polinomial probabilístico de error cero) es la clase de complejidad de los problemas para los que existe una máquina de Turing probabilística con estas propiedades:

• Siempre devuelve la respuesta correcta SÍ o NO.
• El tiempo de funcionamiento es polinomio en expectativa para cada entrada.

En otras palabras, si se permite que el algoritmo lance una moneda verdaderamente aleatoria mientras se está ejecutando, siempre devolverá la respuesta correcta y, para un problema de tamaño n, hay algunos polinomio p(n) tal que el tiempo promedio de ejecución será menor que p(n), aunque ocasionalmente podría ser mucho más largo. Tal algoritmo se llama algoritmo de Las Vegas.

Alternativamente, ZPP se puede definir como la clase de problemas para los cuales existe una máquina de Turing probabilística con estas propiedades:

• Siempre funciona en tiempo polinomio.
• Devuelve una respuesta SÍ, NO o NO SABEN.
• La respuesta es siempre o NO SE O la respuesta correcta.
• Devuelve NO CONOCER con probabilidad en la mayoría de 1/2 por cada entrada (y la respuesta correcta de otra manera).

Las dos definiciones son equivalentes.

La definición de ZPP se basa en máquinas de Turing probabilísticas, pero, para mayor claridad, tenga en cuenta que otras clases de complejidad basadas en ellas incluyen BPP y RP. La clase BQP se basa en otra máquina con aleatoriedad: la computadora cuántica.

Definición de intersección

La clase ZPP es exactamente igual a la intersección de las clases RP y co-RP. Esto se toma a menudo como la definición de ZPP. Para mostrar esto, primero tenga en cuenta que cada problema que está en tanto RP como en co-RP tiene un algoritmo de Las Vegas de la siguiente manera:

• Supongamos que tenemos un idioma L reconocido por ambos RP algoritmo A y el (posiblemente completamente diferente) co-RP algoritmo B.
• Dada una entrada, ejecute A en la entrada para un paso. Si regresa SÍ, la respuesta debe ser SÍ. De lo contrario, ejecute B en la entrada por un paso. Si regresa NO, la respuesta debe ser NO. Si no ocurre, repita este paso.

Tenga en cuenta que solo una máquina puede dar una respuesta incorrecta, y la posibilidad de que esa máquina dé la respuesta incorrecta durante cada repetición es como máximo del 50 %. Esto significa que la posibilidad de llegar a la késima ronda se reduce exponencialmente en k, lo que demuestra que el tiempo de ejecución esperado es polinomial. Esto muestra que RP intersecta co-RP está contenido en ZPP.

Para mostrar que ZPP está contenido en RP intersect co-RP, supongamos que tenemos un algoritmo C de Las Vegas para resolver un problema. Entonces podemos construir el siguiente algoritmo RP:

• Corre C por lo menos doble su tiempo de funcionamiento esperado. Si da una respuesta, da esa respuesta. Si no da ninguna respuesta antes de detenerla, da NO.

Según la desigualdad de Markov, la probabilidad de que dé una respuesta antes de que la detengamos es al menos 1/2. Esto significa que la posibilidad de que demos una respuesta incorrecta en una instancia de SÍ, deteniéndonos y dando NO, es como máximo 1/2, lo que se ajusta a la definición de un algoritmo RP. El algoritmo co-RP es idéntico, excepto que da SÍ si C "se agota el tiempo de espera".

Testimonio y prueba

Las clases NP, RP y ZPP pueden considerarse en términos de prueba de pertenencia a un conjunto.

Definición: Un verificador V para un conjunto X es una máquina de Turing tal que:

• si x está dentro X entonces existe una cuerda w tales que V()x,w) acepta;
• si x no está X, entonces para todas las cuerdas w, V()x,w) rechaza.

La cadena w se puede considerar como la prueba de membresía. En el caso de pruebas cortas (de longitud acotada por un polinomio en el tamaño de la entrada) que se pueden verificar de manera eficiente (V es una máquina de Turing determinista en tiempo polinomial), la cadena w se llama testigo.

Notas:

• La definición es muy asimétrica. La prueba de x estar en X es una sola cadena. La prueba de x no estar en X es la colección de todas las cadenas, ninguna de las cuales es una prueba de la membresía.
• La disponibilidad de testigos es uniforme. Para todos los x en X debe haber un testigo. No es el caso donde ciertas x en X son demasiado difíciles de verificar, mientras que la mayoría no lo son.
• El testigo no necesita ser una prueba tradicionalmente interpretada. Si V es una máquina de Turing probabilista que podría aceptar x si x está en X, entonces la prueba es la cadena de volteretas de monedas que conduce la máquina, por suerte, intuición o genio, a aceptar x.
• El concepto de co-co es una prueba de no pertenencia o pertenencia al conjunto de complementos.

Las clases NP, RP y ZPP son conjuntos que tienen testigos para la pertenencia. La clase NP solo requiere que existan testigos. Pueden ser muy raros. De las 2^f(|x|) cadenas posibles, con f un polinomio, solo una necesita causar el verificador para aceptar (si x está en X. Si x no está en X, ninguna cadena hará que el verificador acepte).

Para las clases RP y ZPP cualquier cadena elegida al azar probablemente será un testigo.

Las co-clases correspondientes tienen testigo para no ser miembro. En particular, co-RP es la clase de conjuntos para los cuales, si x no está en X, es probable que cualquier cadena elegida al azar sea testigo de la no pertenencia. ZPP es la clase de conjuntos para los que es probable que cualquier cadena aleatoria sea testigo de x en X, o de x no en X, cualquiera que sea el caso.

Conectar esta definición con otras definiciones de RP, co-RP y ZPP es fácil. La Máquina de Turing de tiempo polinómico probabilístico V*_w(x) corresponde a la Máquina de Turing de tiempo polinómico determinista V(x, w) reemplazando la cinta aleatoria de V* con una segunda cinta de entrada para V en la que está escrita la secuencia de monedas voltea Al seleccionar el testigo como una cadena aleatoria, el verificador es una Máquina de Turing de tiempo polinómico probabilístico cuya probabilidad de aceptar x cuando x está en X es grande (mayor que 1/2, digamos), pero cero si x ∉ X (para RP); de rechazar x cuando x no está en X es grande pero cero si x ∈ X (para co-RP); y de aceptar o rechazar correctamente a x como miembro de X es grande, pero cero de aceptar o rechazar x incorrectamente (para ZPP).

Mediante la selección aleatoria repetida de un posible testigo, la gran probabilidad de que una cadena aleatoria sea un testigo proporciona un algoritmo de tiempo polinomial esperado para aceptar o rechazar una entrada. Por el contrario, si se espera que la máquina de Turing tenga un tiempo polinomial (para cualquier x dado), entonces una fracción considerable de las ejecuciones debe estar limitada por el tiempo polinomial, y la secuencia de monedas utilizada en tal ejecución será un testigo.

ZPP debe contrastarse con BPP. La clase BPP no requiere testigos, aunque los testigos son suficientes (por lo tanto, BPP contiene RP, co-RP y ZPP). Un lenguaje BPP tiene V(x,w) acepta en una mayoría (clara) de cadenas w si x está en X, y por el contrario rechaza en una mayoría (clara) de cadenas w si x no está en X. Ninguna cadena w necesita ser definitiva y, por lo tanto, en general no pueden considerarse pruebas o testigos.

Propiedades teóricas de la complejidad

Se sabe que ZPP es cerrado bajo complemento; es decir, ZPP = co-ZPP.

ZPP es bajo por sí mismo, lo que significa que una máquina ZPP con el poder de resolver problemas ZPP instantáneamente (una máquina oráculo ZPP) no es más poderosa que la máquina sin este poder adicional. En símbolos, ZPP^ZPP = ZPP.

ZPP^NPBPP = ZPP ^NP.

NP^BPP está contenido en ZPP^NP.

Conexión con otras clases

Dado que ZPP = RP ∩ coRP, ZPP está obviamente contenido en ambos RP y coRP.

La clase P está contenida en ZPP, y algunos informáticos han conjeturado que P = ZPP, es decir, cada algoritmo de Las Vegas tiene un equivalente de tiempo polinomial determinista.

Existe un oráculo relativo al cual ZPP = EXPTIME. Una prueba para ZPP = EXPTIME implicaría que P ≠ ZPP, como P ≠ EXPTIME (ver teorema de jerarquía temporal).