Complexidade da árvore de decisão aleatória entre Las Vegas e Monte Carlo

13

Fundo:

A complexidade da árvore de decisão ou a complexidade da consulta é um modelo simples de computação definido da seguinte maneira. Seja uma função booleana. A complexidade da consulta determinística de f , denotada D ( f ) , é o número mínimo de bits da entrada x { 0 , 1 } n que precisam ser lidos (na pior das hipóteses) por um algoritmo determinístico que calcula f ( x )f:{0 0,1}n{0 0,1}fD(f)x{0 0,1}nf(x). Observe que a medida de complexidade é o número de bits da entrada que são lidos; todos os outros cálculos são gratuitos.

Da mesma forma, definimos a complexidade da consulta aleatória de Las Vegas de , denominada R 0 ( f ) , como o número mínimo de bits de entrada que precisam ser lidos na expectativa por um algoritmo aleatório de erro zero que calcula f ( x ) . Um algoritmo de erro zero sempre gera a resposta correta, mas o número de bits de entrada lidos por ele depende da aleatoriedade interna do algoritmo. (É por isso que medimos o número esperado de bits de entrada lidos.)fR0 0(f)f(x)

Nós definimos a Monte Carlo randomizados consulta complexidade da , denotado R 2 ( f ) , para ser o número mínimo de bits de entrada que precisam ser lidos por um erro delimitada randomizado algoritmo que computa f ( x ) . Um algoritmo de erro delimitada sempre envia uma resposta no final, mas ele só precisa ser correto com maior probabilidade do que 2 / 3 (digamos).fR2(f)f(x)2/3


Questão

O que se sabe sobre a questão de saber se

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

Sabe-se que

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

porque os algoritmos de Monte Carlo são pelo menos tão poderosos quanto os algoritmos de Las Vegas.

Eu aprendi recentemente que não há separação conhecida entre as duas complexidades. A referência mais recente que posso encontrar para esta reivindicação é de 1998 [1]:

[1] Nikolai K. Vereshchagin, árvores de decisão booleanas randomizadas: várias observações, Theoretical Computer Science, volume 207, edição 2, 6 de novembro de 1998, páginas 329-342, ISSN 0304-3975, http://dx.doi.org/ 10.1016 / S0304-3975 (98) 00071-1 .

O limite superior mais conhecido de um em termos de outro é

R0 0(f)=O(R2(f)2registroR2(f))

devido a [2]:

[2] Kulkarni, R. e Tal, A. (2013, novembro). Na sensibilidade do bloco fracionário. In Electronic Colloquium on Computational Complexity (ECCC) (Vol. 20, p. 168).

Eu tenho duas perguntas específicas.

  1. [Pedido de referência]: Existe um artigo mais recente (após 1998) que discute esse problema?
  2. Mais importante , existe uma função candidata conjecturada para separar essas duas complexidades?

Adicionado na v2: Adicionado ref [2], enfatizou a segunda pergunta sobre a existência da função candidata.

Robin Kothari
fonte

Respostas:

7

Até onde eu sei, isso ainda está aberto. Um artigo muito recente que menciona essas quantidades e alguns limites é Aaronson et al: Paridade fraca (ver http://arxiv.org/abs/1312.0036 ). Você também pode ver o capítulo 14 de Jukna: Funções booleanas e a pesquisa de 1999 (ainda bate 1998!) De Buhrman e de Wolf. Outro artigo muito recente sobre a complexidade da árvore de decisão aleatória é Magniez et al: http://arxiv.org/abs/1309.7565

Finalmente, um breve resumo que fiz para mim no mês passado (sem defs):

R2 <= R0 <= D <= n

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

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

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

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

D <= N1 * deg

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

A conjectura de sensibilidade é que s também é polinomialmente relacionado a outros parâmetros.

domotorp
fonte
Você poderia apontar especificamente onde esses documentos fazem referência à questão dos algoritmos Las Vegas vs Monte Carlo? Tentei procurá-lo nesses documentos, mas não o encontrei.
Robin Kothari
Me desculpe se eu era ambíguo, esses trabalhos não mencionam explicitamente a questão, apenas desigualdades diferentes para os diferentes parâmetros. Minha única evidência para a abertura da questão é que, se não fosse, seria mencionada.
Domotorp 25/05
Oh, eu entendo o que você quer dizer. Eu li esses papéis. Eu me pergunto se esse problema foi estudado especificamente mais recentemente. E também estou curioso para saber se existe uma função conjeturada para separar essas duas complexidades. (Ou se as pessoas acreditam que eles são a mesma coisa.)
Robin Kothari
Eu sei que é conjecturado que a maior separação de D é a árvore NAND para R0 e R2.
Domotorp 26/05
7

Esta questão foi resolvida!

f

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

e até mesmo

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

R1(f)

Ambas as separações são ideais até os fatores de log!

Robin Kothari
fonte
Na nova versão de seu artigo, isso foi aprimorado para uma lacuna quase quadrática, que é muito restrita aos fatores de registro.
Shalev