ZPP (complejidad) - ZPP (complexity)
En la teoría de la complejidad , ZPP ( tiempo polinomial probabilístico de error cero ) es la clase de complejidad de 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 ejecución es un polinomio esperado para cada entrada.
En otras palabras, si al algoritmo se le permite lanzar una moneda verdaderamente aleatoria mientras se está ejecutando, siempre devolverá la respuesta correcta y, para un problema de tamaño n , hay algún polinomio p ( n ) tal que el promedio de ejecución el tiempo será menor que p ( n ), aunque ocasionalmente puede 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 que existe una máquina de Turing probabilística con estas propiedades:
- Siempre se ejecuta en tiempo polinomial.
- Devuelve una respuesta SÍ, NO o NO SABE.
- La respuesta es siempre NO SABE o la respuesta correcta.
- Devuelve NO SABE con probabilidad como máximo 1/2 por 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, 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 . A menudo se considera que esta es la definición de ZPP . Para mostrar esto, primero tenga en cuenta que todos los problemas que se encuentran tanto en RP como en co-RP tienen un algoritmo de Las Vegas de la siguiente manera:
- Supongamos que tenemos un lenguaje L reconocido tanto por el algoritmo RP A como por el algoritmo co-RP B (posiblemente completamente diferente) .
- Dada una entrada, ejecute A en la entrada durante un paso. Si devuelve SÍ, la respuesta debe ser SÍ. De lo contrario, ejecute B en la entrada durante un paso. Si devuelve NO, la respuesta debe ser NO. Si no ocurre ninguno, repita este paso.
Tenga en cuenta 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 posibilidad de alcanzar la k- ésima ronda se reduce exponencialmente en k , lo que muestra que el tiempo de ejecución esperado es polinomial. Esto muestra que RP intersect 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. Luego podemos construir el siguiente algoritmo RP :
- Ejecute C durante al menos el doble de su tiempo de ejecución esperado. Si da una respuesta, dé esa respuesta. Si no da ninguna respuesta antes de detenerlo, dé NO.
Según la Desigualdad de Markov , la probabilidad de que dé una respuesta antes de detenerla es de al menos 1/2. Esto significa que la probabilidad de que demos una respuesta incorrecta en una instancia YES, al detenernos y dar NO, es como máximo 1/2, ajustando la definición de un algoritmo RP . El algoritmo co-RP es idéntico, excepto que da SÍ si C "agota el tiempo de espera".
Testigo y prueba
Las clases NP , RP y ZPP se pueden considerar 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 una prueba de pertenencia. En el caso de demostraciones 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 en tiempo polinomial), la cadena w se llama testigo .
Notas:
- La definición es muy asimétrica. La prueba de que x está en X es una sola cadena. La prueba de que x no está en X es la colección de todas las cadenas, ninguna de las cuales es una prueba de pertenencia.
- La disponibilidad de testigos es uniforme. Para todo 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 es.
- El testigo no tiene por qué ser una prueba interpretada tradicionalmente. Si V es una máquina de Turing probabilística que posiblemente podría aceptar x si x está en X, entonces la prueba es la cadena de lanzamientos de monedas que lleva a la máquina, por suerte, intuición o genio, a aceptar x .
- El co-concepto es una prueba de no pertenencia o pertenencia al conjunto complementario.
Las clases NP , RP y ZPP son conjuntos que cuentan con testigos de 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 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á testigo.
Las co-clases correspondientes tienen testigo de no afiliación. 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, ox 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 probabilística de tiempo polinomial 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 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, 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 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 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 sea en tiempo polinomial (para cualquier x dado), entonces una fracción considerable de las corridas debe estar acotada en tiempo polinomial, y la secuencia de monedas utilizada en dicha corrida 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 ). Una BPP lenguaje tiene V (x, w) aceptar en una mayoría (claro) de cadenas w si x está en X, y por el contrario rechazan en una mayoría (claro) de cadenas w si x no está en X . No es necesario que una sola cadena sea definitiva y, por lo tanto, no pueden considerarse en general pruebas o testigos.
Propiedades teóricas de la complejidad
Se sabe que ZPP está cerrado por 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 esta potencia adicional. En símbolos, ZPP ZPP = ZPP .
ZPP NP BPP = ZPP NP .
NP BPP está contenido en ZPP NP .
Conexión a otras clases
Dado que ZPP = RP ∩ coRP , ZPP obviamente está contenido tanto en RP como en 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 polinomio determinista equivalente en tiempo.
Existe un oráculo relativo al cual ZPP = EXPTIME . Una prueba de ZPP = EXPTIME implicaría que P ≠ ZPP , como P ≠ EXPTIME (ver el teorema de la jerarquía de tiempo ).