En una oración: ¿la existencia de una jerarquía para implicaría algún resultado de aleatorización?
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?
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.
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 | ) ) 2
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 )
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 c
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.
fuente
No es difícil derivar una jerarquía de tiempo probabilística si BPP = EXP, el caso extremo de no aleatorización.
fuente