Deje que sea un problema completo de EXP. Entonces, .
Deje que sea cierto oráculo que tiene en cuentas las consultas que (TM en P) hará, y podemos obtener .P B ≠ N P B
Pregunta: ¿Tenemos resultados de oráculo similares para P vs BPP?
Deje que sea un problema completo de EXP. Entonces, .
Deje que sea cierto oráculo que tiene en cuentas las consultas que (TM en P) hará, y podemos obtener .P B ≠ N P B
Pregunta: ¿Tenemos resultados de oráculo similares para P vs BPP?
Respuestas:
Tenía un vago recuerdo de que conocía una excelente referencia para tales separaciones de oráculos. Finalmente lo encontré.
Una gran referencia para las separaciones de oráculo (para clases entre P y PSPACE) es el siguiente documento :
El documento muestra (o da una cita para) una separación de oráculo entre casi todos los pares de clases que podrían interesarle entre P y PSPACE (por ejemplo, tiene clases como P, RP, BPP, UP, FewP, NP, MA, AM , otros niveles de PH, PH, IP, PSPACE, etc.).
Por ejemplo, el Teorema 8 muestra un problema de oráculo en coRP que no está en NP. Como (en relación con todos los oráculos) coRP está en BPP y NP contiene P, tenemos un problema de oráculo en BPP que no está en P.
Como mencioné en mi comentario, mostrar un oráculo para el cual es fácil. Deje que A sea un lenguaje completo de EXP o un lenguaje completo de PSPACE.PA=BPPA
fuente
¡El zoológico de complejidad es tu amigo! Como Robin dijo, tiene la mitad de la respuesta: cualquier problema de EXP completo colapsa NP a P y, por lo tanto, BPP a P. Buhrman y Fortnow construyeron un oráculo en relación con el cual P = RP pero BPP no es igual a P. Esto es más que lo que pediste; Sospecho que hay construcciones más fáciles que separan a P de RP y BPP.
fuente
Greg Kuperberg da una buena descripción de un oráculo que separa P y BPP en uno de los comentarios de esta interesante publicación de blog , donde Terence Tao describe máquinas Turing con oráculos y resultados de complejidad en relación con oráculos en forma de alegoría.
fuente
Bennett & Gill dan oráculos para ambos casos: http://epubs.siam.org/doi/abs/10.1137/0210008
fuente