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 ). 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.)
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).
Questão
O que se sabe sobre a questão de saber se
?
Sabe-se que
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 é
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.
- [Pedido de referência]: Existe um artigo mais recente (após 1998) que discute esse problema?
- 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.
fonte
Esta questão foi resolvida!
e até mesmo
Ambas as separações são ideais até os fatores de log!
fonte