Las Vegas vs Monte Carlo complejidad de árbol de decisión aleatorio

13

Antecedentes:

La complejidad del árbol de decisión o la complejidad de la consulta es un modelo simple de cálculo definido de la siguiente manera. Sea una función booleana. La complejidad de consulta determinista de f , denotada D ( f ) , es el número mínimo de bits de la entrada x { 0 , 1 } n que necesitan ser leídos (en el peor de los casos) por un algoritmo determinista que calcula f ( x )f:{0,1}n{0,1}fD(f)x{0,1}nf(x). Tenga en cuenta que la medida de la complejidad es el número de bits de la entrada que se leen; Todos los demás cálculos son gratuitos.

De manera similar, definimos la complejidad de la consulta aleatoria de Las Vegas de , denotada R 0 ( f ) , como el número mínimo de bits de entrada que deben ser leídos en expectativa por un algoritmo aleatorio de error cero que calcula f ( x ) . Un algoritmo de error cero siempre genera la respuesta correcta, pero el número de bits de entrada leídos depende de la aleatoriedad interna del algoritmo. (Es por eso que medimos el número esperado de bits de entrada leídos).fR0(f)f(x)

Definimos la complejidad de la consulta aleatoria de Monte Carlo de , denotada R 2 ( f ) , como el número mínimo de bits de entrada que debe leer un algoritmo aleatorio de error acotado que calcula f ( x ) . Un algoritmo de error limitado siempre envía una respuesta al final, pero sólo tiene que ser correcta con mayor probabilidad de 2 / 3 (por ejemplo).fR2(F)F(X)2/3


Pregunta

Lo que se sabe sobre la cuestión de si

?R0(f)=Θ(R2(f))

Se sabe que

R0(f)=Ω(R2(f))

porque los algoritmos de Monte Carlo son al menos tan poderosos como los algoritmos de Las Vegas.

Hace poco aprendí que no existe una separación conocida entre las dos complejidades. La última referencia que puedo encontrar para este reclamo es de 1998 [1]:

[1] Nikolai K. Vereshchagin, Árboles de decisión booleanos aleatorizados: varios comentarios, Theoretical Computer Science, Volumen 207, Número 2, 6 de noviembre de 1998, Páginas 329-342, ISSN 0304-3975, http://dx.doi.org/ 10.1016 / S0304-3975 (98) 00071-1 .

El límite superior más conocido de uno en términos del otro es

R0(f)=O(R2(f)2logR2(f))

debido a [2]:

[2] Kulkarni, R. y Tal, A. (noviembre de 2013). Sobre la sensibilidad del bloque fraccional. En Coloquio electrónico sobre la complejidad computacional (ECCC) (Vol. 20, p. 168).

Tengo dos preguntas especificas.

  1. [Solicitud de referencia]: ¿Existe un documento más reciente (después de 1998) que analice este problema?
  2. Más importante aún , ¿hay una función candidata que se conjetura para separar estas dos complejidades?

Agregado en v2: Añadido ref [2], enfatizó la segunda pregunta sobre la existencia de la función candidata

Robin Kothari
fuente

Respuestas:

7

Que yo sepa, esto todavía está abierto. Un artículo muy reciente que menciona estas cantidades y algunos límites es Aaronson et al: Paridad débil (ver http://arxiv.org/abs/1312.0036 ). También puede ver el capítulo 14 de Jukna: funciones booleanas y la encuesta de 1999 (¡todavía supera a 1998!) De Buhrman y de Wolf. Otro artículo muy reciente sobre la complejidad del árbol de decisión aleatorio es Magniez et al: http://arxiv.org/abs/1309.7565

Finalmente, un breve resumen que hice para mí el mes pasado (sin defs):

R2 <= R0 <= D <= n

D <= N0 * N1 <= C ^ 2 <= R0 ^ 2

s <= bs <= C <= s * bs <= bs ^ 2 (nuevo: [Gilmer-Saks-Srinivasan]: hay f st bs ^ 2 (f) = O (C (f)))

D <= N1 * bs <= bs ^ 3 <= (3R2) ^ 3

deg <= D <= bs * deg <= deg ^ 3 (nuevo: [Tal]: bs <= deg ^ 2)

D <= N1 * deg

C <= bs * deg ^ 2 <= deg ^ 4

La conjetura de sensibilidad es que s también está polinomialmente relacionada con otros parámetros.

domotorp
fuente
¿Podría señalar específicamente dónde estos documentos hacen referencia a la pregunta de Las Vegas vs algoritmos de Monte Carlo? Traté de buscarlo en estos documentos pero no pude encontrarlo.
Robin Kothari
Lamento haber sido ambiguo, estos documentos no mencionan explícitamente la pregunta, solo diferentes desigualdades para los diferentes parámetros. Mi única evidencia de la apertura de la pregunta es que si no fuera así, se mencionaría.
domotorp
Oh, entiendo lo que quieres decir. He leído estos papeles. Sin embargo, me pregunto si este problema se ha estudiado específicamente más recientemente. Y también tengo curiosidad por saber si hay una función que se conjetura para separar estas dos complejidades. (O si la gente cree que son iguales.)
Robin Kothari
Sé que se conjetura que la mayor separación de D es el árbol NAND para R0 y R2.
domotorp
7

Esta pregunta ha sido resuelta!

F

R0 0(F)=Ω~(R2(F)2)

e incluso

R0 0(F)=Ω~(R1(F)2)

R1(F)

¡Ambas separaciones son óptimas hasta factores de registro!

Robin Kothari
fuente
En la nueva versión de su documento, esto se ha mejorado a una brecha casi cuadrática, que está estrechamente relacionada con los factores de registro.
Shalev