Jerarquía para BPP vs desrandomización

29

En una oración: ¿la existencia de una jerarquía para implicaría algún resultado de aleatorización?BPTIME

Una pregunta relacionada pero más vaga es: ¿la existencia de una jerarquía para implica algún inferior difícil? ¿La resolución de este problema choca contra una barrera conocida en la teoría de la complejidad?BPTIME

Mi motivación para esta pregunta es comprender la dificultad relativa (con respecto a otros problemas abiertos importantes en la teoría de la complejidad) de mostrar una jerarquía para . Supongo que todos creen que existe tal jerarquía, pero corríjame si piensa lo contrario.BPTIME

Algunos antecedentes : contiene aquellos idiomas cuya membresía puede ser decidida por una máquina de torneado probabilística en el tiempo con probabilidad limitada de error. Más precisamente, un lenguaje si existe una máquina Turing probabilística tal que para cualquier la máquina ejecuta en el tiempo y acepta con probabilidad al menos , y para cualquier , corre en el tiempo y rechaza con probabilidad al menos .f ( n ) L B P T I M E ( f ( n ) ) T x L T O ( f ( | x | ) ) 2 / 3 x L T O ( f ( | x | ) ) 2BPTIME(f(n))f(n)LBPTIME(f(n))TxLTO(f(|x|))2/3xLTO(f(|x|))2/3

Incondicionalmente, está abierto si para todo . Barak demostró que existe una estricta jerarquía para para máquinas con consejos . Fortnow y Santhanam mejoraron esto a 1 bit de consejos. Esto me lleva a pensar que probar la existencia de una jerarquía de tiempo probabilística no está tan lejos. Por otro lado, el resultado aún está abierto y no puedo encontrar ningún progreso después de 2004. Las referencias, como de costumbre, se pueden encontrar en el zoológico .c > 1 B P T I M E O ( log n )BPTIME(nc)BPTIME(n)c>1BPTIMEO(logn)

La relación con la desradiación proviene de los resultados de Impagliazzo y Wigderson: mostraron que bajo un supuesto de complejidad plausible, para cualquier constante y alguna constante . Según los teoremas clásicos de la jerarquía temporal para el tiempo determinista, esto implica una jerarquía temporal para el tiempo probabilístico. Estoy haciendo la pregunta inversa: ¿una jerarquía probabilística golpea contra una barrera relacionada con la prueba de resultados de desrandomización?d cBPTIME(nd)DTIME(nc)dc


EDITAR: Estoy aceptando la respuesta de Ryan como una solución más completa.

Si alguien tiene observaciones sobre lo que se interpone entre nosotros y demuestra la existencia de una jerarquía para el tiempo probabilístico, no dude en responder / comentar. Por supuesto, la respuesta obvia es que tiene una definición semántica que desafía las técnicas clásicas. Estoy interesado en observaciones menos obvias.BPTIME

Sasho Nikolov
fuente

Respuestas:

22

Sea PTH la hipótesis de que existe una jerarquía de tiempo probabilística. Suponga que la respuesta a su pregunta es verdadera, es decir, "PTH implica " para alguna fija . Entonces, sería incondicionalmente cierto. Considere dos casos:c E X P B P PBPPTIME[2nc]cEXPBPP

  • Si PTH es falso, entonces . Este es el contrapositivo de lo que Lance notó.EXPBPP
  • Si PTH es verdadero, entonces "PTH implica ", así que nuevamente .E X P B P PBPPTIME[2nc]EXPBPP

De hecho, incluso una desrandomización infinitamente frecuente de BPP bajo PTH implicaría incondicionalmente. Entonces, cualesquiera que sean las barreras que se apliquen para probar , se aplican a las declaraciones de prueba del tipo "PTH implica desrandomización".E X P B P PEXPBPPEXPBPP

Ryan Williams
fuente
3
Agradable. Por lo tanto, existe una fuerte barrera contra la demostración de que existe una barrera relacionada con la desrandomización para probar la PTH.
Sasho Nikolov
18

No es difícil derivar una jerarquía de tiempo probabilística si BPP = EXP, el caso extremo de no aleatorización.

Lance Fortnow
fuente
2
Y no necesita BPP = EXP, solo necesita BPP no en DTIME (2 ^ {n ^ c)}) para una constante c> 1. Es decir, solo necesita que BPP sea difícil para DTIME, no ese BPP puede resolver lenguajes E-complete. Esto dice que la extrema falta de aleatorización implica una jerarquía. ¿Qué pasa con la falta intermedia de desrandomización?
Jeff Kinne
Buenas observaciones Entonces, un colapso hacia arriba es tan bueno como un colapso hacia abajo para establecer una jerarquía. Esto socava mi motivación, pero, técnicamente hablando, ¿no es posible que una jerarquía probabilística implique desrandomización, aunque la falta de aleatorización implique una jerarquía probabilística (una declaración falsa puede implicar una declaración verdadera)? La pregunta más vaga sobre las barreras que enfrenta el problema de la jerarquía de BPP sigue en pie. Por ejemplo, es posible que BPP tenga una jerarquía para todos los oráculos (la pregunta no resuelta de Fortnow-Sipser'89), ¿entonces la relativización no es un problema?
Sasho Nikolov