¿Se sabe si

10

La inclusión inversa es obvia, como lo es el hecho de que cualquier lenguaje NP auto reducible en BPP también está en RP. ¿También se sabe que esto es válido para idiomas NP no auto-reducibles?

bppcapnpvsrp
fuente
2
Si se supiera, a partir de las inclusiones RPBPP y RPNP , se deduciría que BPP=RP o RP=NP (o ambos, dependiendo esencialmente de la relación entre BPP y NP Entonces, creo que es seguro asumir que actualmente se desconoce. Dado que RP tiene un error unilateral, es fácil ver cómo está contenido en BPP, sin necesidad de auto-reducibilidad o cualquier otra propiedad.
chazisop
44
Lo que se sabe es que NPBPP implica NP = RP. @chazisop, ¿de dónde sacaste que NPBPP=RP implica BPP = RP o NP = RP?
Emil Jeřábek
1
Supongamos que conocemos BPPNPRP(1) . Entonces podemos hacer análisis de casos: - Si BPPNP , a continuación, a partir de (1) NPRP , que con resultados conocidos implica NP=RP . - Si NPBPP , entonces de (1) BPPRP , que con resultados conocidos implica BPP=RPNPBPPBPPNP=RP
44
Tienes los dos primeros casos mezclados. Más importante aún, en el tercer caso genérico, su conclusión es idéntica a la suposición, por lo que todo el argumento no logra nada. En particular, no admite el reclamo incorrecto en su primer comentario.
Emil Jeřábek
1
La suposición solo pide el subconjunto, no la igualdad. En cualquier caso, mi argumento (incluso mal formateado y con errores) muestra que si supiéramos lo que se pregunta, podríamos derivar relaciones de clase de complejidad que actualmente son problemas abiertos. Además, no veo cómo el tercer caso es más genérico que el resto: excluye explícitamente la posibilidad de que una clase contenga la otra, que actualmente se desconoce.
chazisop

Respuestas:

7

Como con la mayoría de las preguntas en complejidad, no estoy seguro de que haya una respuesta completa durante mucho tiempo. Pero al menos podemos mostrar que la respuesta no es relativizante: hay un oráculo relativo a la desigualdad y uno relativo a la igualdad. Es bastante fácil dar un oráculo con respecto al cual las clases son iguales: cualquier oráculo que tenga funcionará (por ejemplo, cualquier oráculo con respecto al cual "la aleatoriedad no ayuda mucho"), como cualquier oráculo que tenga (por ejemplo, cualquier oráculo en relación con el cual "la aleatoriedad ayuda mucho"). Hay muchos de estos, así que no me molestaré con los detalles.BPP=RPNPBPP

Es un poco más difícil, aunque todavía bastante sencillo, diseñar un oráculo en relación con el cual obtenemos . La construcción a continuación en realidad funciona un poco mejor: para cualquier constante , hay un oráculo en relación con el cual hay un lenguaje en que no está en . Lo resumiré a continuación.RPBPPNPccoRPUPRPTIME[2nc]

Diseñaremos un oráculo que contenga cadenas de la forma , donde es una cadena de bits, es un solo bit y es una cadena de bits de longitud . También le daremos un lenguaje que será decidido por una máquina y una máquina la siguiente manera:A(x,b,z)xnbz2ncLAcoRPUP

  • La máquina , en la entrada , adivina de longitud al azar, consulta y copia la respuesta.coRPxz2|x|c(x,0,z)
  • La máquina , en la entrada , adivina de longitud , consulta y copia la respuesta.UPxz2|x|c(x,1,z)

Para que las máquinas especificadas anteriormente realmente cumplan sus promesas, necesitamos para satisfacer algunas propiedades. Para cada , una de estas dos opciones debe ser el caso:Ax

  • Opción 1: En más de la mitad de opciones tener y cero opciones tener . (En este caso, )z(x,0,z)A z(x,1,z)AxLA
  • Opción 2: Cada elección tiene y precisamente uno elección tiene . (En este caso, )z(x,0,z)A z(x,1,z)AxLA

Nuestro objetivo será especificar satisfaga estas promesas para que diagonalice contra cada . Para tratar de mantener corta esta respuesta ya larga, dejaré caer la maquinaria de construcción de Oracle y muchos de los detalles sin importancia, y explicaré cómo diagonalizar contra una máquina en particular. Fix un estudio aleatorizado máquina de Turing, y dejar que sea una entrada de modo que tenemos un control total sobre la selección de 's y ' s de manera que . Romperemos en .ALARPTIME[2nc]Mxbz(x,b,z)AMx

  • Caso 1: Suponga que hay una manera de seleccionar las 's para que satisfaga la primera opción de su promesa, y tenga una opción de aleatoriedad que acepte. Entonces comprometeremos a esta selección. Entonces no puede satisfacer simultáneamente la promesa y rechazar . No obstante, . Así que hemos diagonalizada contra .zAMAMRPxxLAM

  • Caso 2: A continuación, suponga que el caso anterior no funcionó. Ahora mostraremos que entonces puede verse obligado a romper la promesa o rechazar alguna elección de satisfaga la segunda opción de su promesa. Este diagonaliza contra . Haremos esto en dos pasos:MRPAM

    1. Muestran que para cada elección fijo de bits aleatorios 's, debe rechazar cuando todos sus consultas de la forma están en y todas sus consultas de la forma no están en .rMM(x,0,z)A(x,1,z)A
    2. Demostramos que podemos dar la vuelta una respuesta de por alguna elección de sin afectar a la probabilidad de aceptación de por mucho.(x,1,z)AzM

    De hecho, si comenzamos con desde el paso 1, la probabilidad de aceptación de es cero. no satisface la segunda opción de su promesa, pero luego podemos voltear un solo bit como en el paso 2 y lo hará. Dado que voltear el bit hace que la probabilidad de aceptación de permanezca cerca de cero, se deduce que no puede aceptar simultáneamente y satisfacer la promesa .AMAMMxRP

Queda por discutir los dos pasos en el caso 2:

  1. Fijar una selección de bits aleatorios para . Ahora Simular usando como la aleatoriedad y responder a las consultas de forma que y . Observe que realiza como máximo consultas. Como hay opciones de , podemos arreglar las opciones no consultadas de para tener , y hacer que satisfaga la primera opción de Es una promesa. Como no pudimos hacer que el Caso 2 funcione para , esto significarMMr(x,0,z)A(x,1,z)AM2nc22nczz(x,0,z)AAMMdebe rechazar todas sus elecciones de aleatoriedad en relación con , y en particular con . Se deduce que si seleccionamos para tener y para cada opción de , entonces para cada opción de bits aleatorios , rechaza respecto a .ArA(x,0,z)A(x,1,z)AzrMA

  2. Suponga que para cada , la fracción de bits aleatorios para los que consulta es al menos . Entonces el número total de consultas es al menos . Por otro lado, realiza como máximo consultas en todas sus ramas, una contradicción. Por lo tanto, hay una opción de para que la fracción de bits aleatorios para los que consulta sea ​​menor que 1/2. Por lo tanto, cambiar el valor de en esta cadena afecta la probabilidad de aceptación de en menos de .zM(x,1,z)1/222nc22nc/2M22nc2nczM(x,1,z)AM1/2

Andrew Morgan
fuente
Esta respuesta es bastante larga y probablemente se beneficiaría de un enlace a un recurso externo que ofrezca una mejor explicación de las técnicas involucradas. Si alguien sabe de uno, felizmente lo incluiré.
Andrew Morgan
Podría estar en la encuesta de Ko.
Kaveh
1
@Kaveh: Miré esta encuesta (es a la que te refieres, ¿verdad?), Pero no noté mucho que parezca inmediatamente relevante. La mayoría de los resultados parecían caer en el caso de probar . Un punto notable es que relación con un oráculo aleatorio, por lo que obtenemos relación con un oráculo aleatorio. BPPNP=RPP=RPBPPNP=RP
Andrew Morgan