Alterne entre tempo e complexidade da consulta

Trabalhar diretamente com complexidade de tempo ou limitar os limites inferiores do circuito é assustador. Por isso, desenvolvemos ferramentas como complexidade da consulta (ou complexidade da árvore de decisão) para lidar com limites inferiores. Como cada consulta executa pelo menos uma etapa da unidade e os cálculos entre as consultas são contados como livres, a complexidade do tempo é tão alta quanto a complexidade da consulta. No entanto, podemos dizer algo sobre as separações?

Estou curioso sobre o trabalho na literatura clássica ou quântica, mas forneço exemplos do CQ, pois sou mais familiar.

Alguns algoritmos famosos, como a pesquisa de Grover e a descoberta de períodos de Shor, a complexidade do tempo está dentro dos fatores poliolarítmicos da complexidade da consulta. Para outros, como o Problema do subgrupo oculto, temos complexidade de consulta polinomial , mas os algoritmos de tempo polinomial não são conhecidos.

Como existe uma lacuna potencialmente entre o tempo e a complexidade da consulta, não está claro que um algoritmo de complexidade do tempo ideal precise ter a mesma complexidade de consulta que o algoritmo de complexidade da consulta ideal.

Existem exemplos de trade-offs entre tempo e complexidade da consulta?

Existem problemas em que o algoritmo de complexidade de tempo mais conhecido tem uma complexidade de consulta diferente do algoritmo de complexidade de consulta mais conhecido? Em outras palavras, podemos realizar mais consultas para facilitar as operações entre consultas?

Ou existe um argumento que mostra que sempre existe uma versão de um algoritmo de consulta assintoticamente ideal com uma implementação com a melhor complexidade de tempo assintoticamente?

Aqui está uma tentativa de criar uma função artificial com a seguinte propriedade:

• O problema pode ser resolvido com consultas, mas requer tempo.exp ( n $O(\log n)$$\exp(n)$
• O problema pode ser resolvido com o tempo mas isso requer consultasO ( n $O(n)$$O(n)$

Deixe o tamanho da entrada ser . Deixe os primeiros bits (vamos chamar essa cadeia x) codificar a entrada para um problema completo para o EEXP. Os próximos bits (vamos chamar essa string de y) têm a propriedade de que todos são zero se e somente se x for uma instância NO do problema de EEXP-complete.log n $n + \log n$$\log n$$n$

Em palavras, os primeiros bits codificam um problema difícil e os próximos bits fornecem uma pista sobre a solução do problema. No entanto, para descobrir a solução, observe a seqüência de bits que você faz consultas .n n Ω ( n $\log n$$n$$n$$\Omega(n)$

Portanto, esse problema pode ser resolvido lendo apenas os primeiros bits e gastando o tempo exp (n) ou lendo bits e usando apenas o tempo linear.$\log n$$n$

A mesma função passa pela complexidade da consulta quântica. Insira sinais de raiz quadrada sempre que necessário.

Uma versão mais extrema do exemplo de Robin:

Deixe o tamanho da entrada ser , com os primeiros bits (chame essa sequência ) codificando uma máquina de Turing . Corrija alguma função . Deixe o último bit da string ser se a máquina de Turing em menos de etapas. O problema é determinar se pára em menos de etapas e a paridade de é par.n - $n$$n-1$T x f ( n ) 1 T x f ( n ) T x f ( n ) $x$$T_x$$f(n)$$1$$T_x$$f(n)$$T_x$$f(n)$$x$

Assim, fazendo consultas, o problema pode ser resolvido no tempo , enquanto fazendo consultas, o problema pode ser resolvido no tempo .O ( f ( n ) ) $n-1$$O(f(n))$$n$$O(n)$

Gosto da resposta de Robin Kothari e da modificação de Joe Fitzsimons. Em uma extensão óbvia de suas respostas, eles podem atingir qualquer taxa de separação (exceto constante versus não constante) entre a complexidade da consulta cada vez menor e maior e a complexidade do tempo cada vez menor. No entanto, não há maneira óbvia de tornar suas funções não parciais. Quero apontar um problema natural em que temos uma separação e mostrar que grandes separações são mais difíceis para funções totais.

Um problema natural

Ben Reichardt apontou por e-mail o problema de avaliação da fórmula. A complexidade da consulta quântica para avaliar uma fórmula geral AND-OR de leitura única em variáveis ​​é . No entanto, o algoritmo de consulta economiza tempo. Aqui , o algoritmo conhecido mais rápido é mostrado para fazer consultas e executar no tempo polilogaritmicamente pior. Assim, temos um problema total natural onde existe uma separação conhecida. Embora não haja provas de que essa separação tenha que existir.$n$$\Theta(\sqrt{n})$$O(\sqrt{n})$$O(\sqrt{n}\log{n})$

Total de funções são mais difíceis de separar?

Para mim, parece mais difícil encontrar funções totais com separações prováveis. Para mostrar que o caso de funções totais e parciais é diferente, apresentarei um argumento sobre a maior separação entre as complexidades da consulta dos algoritmos de consulta ótima e ótima para uma função total.

Usando o limite inferior [1] de Simon, podemos ver que se uma função depende de de suas variáveis, precisaremos consultar pelo menos deles. Por outro lado, o máximo que poderíamos consultar é . Observe que não há razão para consultar todas as variáveis, porque a saída é independente de delas (chame esses bits mortos) e, para uma função total, nenhuma estrutura secreta será revelada observando esses bits mortos. Assim, mesmo o algoritmo mais otimizado no tempo para uma função total pode ser modificado para usar no máximo consultas, assumindo simplesmente que os bits mortos são todos .$m$$\Omega{(\log m)}$$m$$n$$n - m$$m$$0$

Portanto, se escrevermos , obteremos uma função total, considerando o algoritmo ideal para consultas com complexidade , existe um algoritmo de tempo-óptima com complexidade com e . Em outras palavras, não podemos ter mais do que uma separação exponencial na complexidade da consulta entre os algoritmos de consulta ideal e de tempo ótimo para funções totais. Eu não ficaria surpreso se esses limites realmente frouxos pudessem ser melhorados.( q 1 ( n ) , t 1 ( n ) ) ( q 2 ( n ) , t 2 ( n ) ) q 2 ( n ) ≤ f ( q 1 ( n ) ) f ( n ) = O ( 2 n$(\text{query complexity}\; , \; \text{time complexity})$$(q_1(n),t_1(n))$$(q_2(n),t_2(n))$$q_2(n) \leq f(q_1(n))$$f(n) = O(2^n)$

[1] HU Simon, "Um limite apertado de Z (loglogn) na hora em que RAMs paralelas calculam funções booleanas não degeneradas", em: Symp. em Fundamentos da Teoria da Computação, Lecture Notes in Computer Science, vol. 158, Springer, Berlim, 1983, pp. 439-444.