Wymień czas i złożoność zapytań

Praca bezpośrednio ze złożonością czasu lub dolnymi granicami obwodu jest przerażająca. Dlatego opracowujemy narzędzia takie jak złożoność zapytań (lub złożoność drzewa decyzyjnego), aby uzyskać kontrolę nad dolnymi granicami. Ponieważ każde zapytanie zajmuje co najmniej jeden krok jednostkowy, a obliczenia między zapytaniami są liczone jako wolne, złożoność czasu jest co najmniej tak wysoka jak złożoność zapytania. Czy możemy jednak powiedzieć coś o separacjach?

Jestem ciekawy pracy w literaturze klasycznej lub kwantowej, ale dostarczam przykłady z QC, ponieważ jestem bardziej zaznajomiony.

Niektóre słynne algorytmy, takie jak wyszukiwanie Grovera i wyszukiwanie okresów Shora, złożoność czasowa mieści się w zakresie czynników logarytmicznych złożoności zapytania. W przypadku innych, takich jak problem ukrytej podgrupy, mamy wielomianową złożoność zapytań , ale algorytmy wielomianu czasu nie są znane.

Ponieważ potencjalnie istnieje luka między złożonością czasu a złożonością zapytania, nie jest jasne, czy algorytm optymalnej złożoności czasu musi mieć taką samą złożoność zapytania, jak algorytm optymalnej złożoności zapytania.

Czy istnieją przykłady kompromisów między czasem a złożonością zapytań?

Czy występują problemy, w których najbardziej znany algorytm złożoności czasu ma inną złożoność zapytań niż najbardziej znany algorytm złożoności zapytań? Innymi słowy, czy możemy wykonać więcej zapytań, aby ułatwić operacje między zapytaniami?

Czy może istnieje argument, który pokazuje, że zawsze istnieje wersja asymptotycznie optymalnego algorytmu zapytań posiadająca implementację o asymptotycznie najlepszej złożoności czasowej?

Oto próba utworzenia sztucznej funkcji o następującej właściwości:

• Problem można rozwiązać za pomocą zapytań , ale wymaga czasu.$O(\log n)$$\exp(n)$
• Problem można rozwiązać za pomocą czasu ale wymaga to zapytań$O(n)$$O(n)$

Niech rozmiar wejściowy to . Niech pierwsze bity (nazwijmy ten ciąg x) kodują dane wejściowe do pełnego problemu dla EEXP. Następne bitów (nazwijmy ten ciąg y) ma właściwość polegającą na tym, że wszystkie mają wartość zero wtedy i tylko wtedy, gdy x jest NIE wystąpieniem problemu EEXP-complete.$n + \log n$$\log n$$n$

Innymi słowy, pierwsze bity kodują trudny problem, a następne bitów daje wskazówkę dotyczącą rozwiązania problemu. Jednak, aby znaleźć rozwiązanie, patrząc na bitowy ciąg, wykonujesz zapytania .n n Ω ( n $\log n$$n$$n$$\Omega(n)$

Tak więc problem ten można rozwiązać albo czytając tylko pierwsze n i spędzając czas exp (n), albo czytając n bitów i używając tylko czasu liniowego.$\log n$$n$

Ta sama funkcja dotyczy złożoności kwantowych zapytań. W razie potrzeby wstaw znaki pierwiastka kwadratowego.

Bardziej ekstremalna wersja przykładu Robina:

Niech rozmiar wejściowy będzie , przy czym pierwsze n - 1 bitów (nazywamy ten ciąg x ) koduje maszynę Turinga T x . Napraw niektóre funkcje f ( n ) . Niech ostatni bit struny będzie wynosić 1 w maszynie Turinga T x zatrzymuje się w krokach mniejszych niż f ( n ) . Problem polega zatem na ustaleniu, czy T x zatrzymuje się w krokach mniejszych niż f ( n ), a parzystość x jest parzysta.$n$$n-1$$x$$T_x$$f(n)$$1$$T_x$$f(n)$$T_x$$f(n)$$x$

Tak więc, wykonując zapytań, problem można rozwiązać w czasie O ( f ( n ) ) , podczas gdy wykonując n zapytań, problem można rozwiązać w czasie O ( n ) .$n-1$$O(f(n))$$n$$O(n)$

Podoba mi się odpowiedź Robina Kothari i modyfikacja Joe Fitzsimonsa. W oczywisty sposób rozszerzając swoje odpowiedzi mogą osiągnąć dowolny stosunek separacji (oprócz stałej względem nie-stałej) między coraz mniejszą złożonością zapytań a coraz większą złożonością czasową. Jednak nie ma oczywistego sposobu, aby ich funkcje nie były częściowe. Chcę wskazać na naturalny problem, w którym mamy separację i pokazać, że duże separacje są trudniejsze dla wszystkich funkcji.

Naturalny problem

Ben Reichardt zwrócił uwagę na e-mail na problem oceny formuły. Złożoność kwantowych zapytań do oceny ogólnej formuły AND-OR do jednorazowego odczytu dla zmiennych wynosi Θ ( $n$. JednakO($\Theta(\sqrt{n})$Algorytm zapytania nie jest wydajny czasowo. Tutajpokazano najszybszy znany algorytm, który tworzyO($O(\sqrt{n})$zapytania i uruchamiane w czasie polilogarytmicznie gorzej. Mamy zatem naturalny problem całkowity, w którym występuje znany rozdział. Chociaż nie ma dowodów na to, że ten rozdział musi istnieć.$O(\sqrt{n}\log{n})$

Trudno jest rozdzielić wszystkie funkcje?

Wydaje mi się, że trudniej jest znaleźć funkcje całkowite z możliwymi do udowodnienia rozdzieleniami. Aby pokazać, że przypadek funkcji całkowitych i częściowych jest inny, przedstawię argument dotyczący największej separacji pomiędzy złożonością zapytań algorytmów optymalnych i optymalnych czasowo dla funkcji całkowitej.

$m$$\Omega{(\log m)}$$m$$n$$n - m$$m$$0$

$(\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, „Ciasny Z (loglogn) związany z czasem, w którym równoległe pamięci RAM obliczają nie-zdegenerowane funkcje boolowskie”, w: Symp. na temat podstaw teorii obliczeń, notatki z wykładów z informatyki, t. 158, Springer, Berlin, 1983, ss. 439–444.