ZPP (complejidad)

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

• Siempre devuelve la respuesta correcta, SÍ o NO.
• El tiempo de ejecución es polinómico en promedio para cada entrada.

En otras palabras, si se permite que el algoritmo lance una moneda al azar mientras se ejecuta, siempre devolverá la respuesta correcta y, para un problema de tamaño n , existe un polinomio p ( n ) tal que el tiempo de ejecución promedio será menor que p ( n ), aunque ocasionalmente pueda ser mucho mayor. Este tipo de algoritmo se denomina algoritmo de Las Vegas .

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

• Siempre se ejecuta en tiempo polinomial.
• Devuelve una respuesta SÍ, NO o NO LO SÉ.
• La respuesta siempre es NO LO SÉ o la respuesta correcta.
• Devuelve NO LO SÉ con una probabilidad máxima de 1/2 para cada entrada (y la respuesta correcta en caso contrario).

Las dos definiciones son equivalentes.

La definición de ZPP se basa en máquinas de Turing probabilísticas, pero, para mayor claridad, cabe señalar 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 .

La clase ZPP es exactamente igual a la intersección de las clases RP y co-RP . Esto se suele considerar la definición de ZPP . Para demostrarlo, observemos primero que todo problema que pertenece tanto a RP como a co-RP tiene un algoritmo de Las Vegas como sigue:

• Supongamos que tenemos un lenguaje L reconocido tanto por el algoritmo RP A como por el algoritmo co-RP B (posiblemente completamente diferente).
• Dado un dato de entrada, ejecute la función A sobre dicho dato durante un paso. Si devuelve SÍ, la respuesta debe ser SÍ. De lo contrario, ejecute la función B sobre dicho dato durante un paso. Si devuelve NO, la respuesta debe ser NO. Si no se cumple ninguna de las dos condiciones, repita este paso.

Nótese que solo una máquina puede dar una respuesta incorrecta, y la probabilidad de que esa máquina dé una respuesta incorrecta durante cada repetición es como máximo del 50%. Esto significa que la probabilidad de llegar a la k -ésima ronda disminuye exponencialmente con k , lo que demuestra que el tiempo de ejecución esperado es polinómico. Esto demuestra que RP intersect co-RP está contenido en ZPP .

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

• Ejecuta C durante al menos el doble de su tiempo de ejecución previsto. Si da una respuesta, proporciona esa respuesta. Si no da ninguna respuesta antes de que lo detengamos, indica NO.

Según la desigualdad de Markov , la probabilidad de que dé una respuesta antes de que lo detengamos es de al menos 1/2. Esto significa que la probabilidad de que demos una respuesta incorrecta en un caso de SÍ, al detenernos y dar 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 "agota el tiempo".

Las clases NP , RP y ZPP pueden entenderse 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á en X, entonces existe una cadena w tal que V ( x , w ) acepta;
• Si x no está en X , entonces para todas las cadenas w , V ( x , w ) rechaza.

La cadena w puede considerarse como la prueba de pertenencia. En el caso de pruebas cortas (de longitud limitada por un polinomio en el tamaño de la entrada) que pueden verificarse eficientemente ( V es una máquina de Turing determinista de tiempo polinomial), la cadena w se denomina testigo .

Notas:

• La definición es muy asimétrica. La prueba de que x pertenece a X es una sola cadena. La prueba de que x no pertenece a X es el conjunto de todas las cadenas, ninguna de las cuales constituye una prueba de pertenencia.
• Para todo x en X debe haber un testigo de su pertenencia a X.
• El testigo no tiene por qué ser una prueba interpretada tradicionalmente. Si V es una máquina de Turing probabilística que podría aceptar x si x pertenece a X, entonces la prueba es la secuencia de lanzamientos de moneda que lleva a la máquina a aceptar x (siempre que todos los miembros de X tengan algún testigo y la máquina nunca acepte un elemento que no pertenezca a X).
• El concepto de co-relación es una prueba de no pertenencia, o de pertenencia al conjunto complementario.

Las clases NP , RP y ZPP son conjuntos que tienen testigos para la pertenencia. La clase NP solo requiere que existan testigos. Estos pueden ser muy raros. De las 2 ^{f (| x |)} cadenas posibles, donde f es un polinomio, solo una debe hacer que el verificador acepte (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 testigos de no pertenencia. En particular, co-RP es la clase de conjuntos para los cuales, si x no está en X, cualquier cadena elegida al azar probablemente sea un testigo de no pertenencia. ZPP es la clase de conjuntos para los cuales cualquier cadena aleatoria probablemente sea un testigo de que x está en X, o de que x no está en X, según sea el caso.

Conectar esta definición con otras definiciones de RP , co-RP y ZPP es fácil. La máquina de Turing probabilística de tiempo polinomial V* _w ( x ) corresponde a la máquina de Turing determinista de tiempo polinomial 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 lanzamientos de moneda. Al seleccionar el testigo como una cadena aleatoria, el verificador es una máquina de Turing probabilística de tiempo polinomial cuya probabilidad de aceptar x cuando x está en X es grande (mayor que 1/2, por ejemplo), 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 x como miembro de X es grande, pero cero de aceptar o rechazar incorrectamente x (para ZPP ).

Mediante la selección aleatoria repetida de un posible testigo, la alta 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 un tiempo polinomial, y la secuencia de monedas utilizada en dicha ejecución será un testigo.

Se debe contrastar ZPP con BPP . La clase BPP no requiere testigos, aunque estos 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 a la inversa rechaza en una mayoría (clara) de cadenas w si x no está en X. Ninguna cadena w individual tiene por qué ser definitiva, y por lo tanto, en general, no pueden considerarse pruebas ni testigos.

ZPP es cerrado bajo el complemento, es decir, ZPP = co- ZPP (esto se deduce de ZPP = RP ∩ co- RP ).

ZPP es bajo en sí mismo, lo que significa que una máquina ZPP con la capacidad de resolver problemas ZPP instantáneamente (una máquina oráculo ZPP) no es más potente que la máquina sin esta capacidad adicional. En símbolos, ZPP ^ZPP = ZPP .

ZPP ^{NP BPP} = ZPP ^NP .

NP ^BPP está contenido en ZPP ^NP .

Dado que ZPP = RP ∩ coRP , es obvio que ZPP está contenido tanto en RP como en coRP .

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

Existe un oráculo con respecto al cual ZPP = EXPTIME . ^{[ 1 ]} Una demostración de que ZPP = EXPTIME implicaría que P ≠ ZPP , ya que P ≠ EXPTIME (véase el teorema de jerarquía temporal ).

• BPP
• rol

• Zoológico de complejidad : Clase ZPP ZPP