Compromis entre le temps et la complexité des requêtes

Travailler directement avec la complexité du temps ou les limites inférieures du circuit est effrayant. Par conséquent, nous développons des outils tels que la complexité des requêtes (ou la complexité de l'arbre de décision) pour comprendre les limites inférieures. Étant donné que chaque requête prend au moins une étape unitaire et que les calculs entre les requêtes sont comptés comme gratuits, la complexité temporelle est au moins aussi élevée que la complexité de la requête. Cependant, pouvons-nous dire quelque chose sur les séparations?

Je suis curieux de travailler dans la littérature classique ou quantique, mais je fournis des exemples de QC car je suis plus familier.

Certains algorithmes célèbres tels que la recherche de Grover et la découverte de la période de Shor, la complexité temporelle est dans les facteurs poly-logarithmiques de la complexité de la requête. Pour d'autres, comme le problème des sous-groupes cachés, nous avons une complexité de requête polynomiale , mais les algorithmes temporels polynomiaux ne sont pas connus.

Étant donné qu'un écart existe potentiellement entre le temps et la complexité de la requête, on ne sait pas qu'un algorithme de complexité de temps optimal doit avoir la même complexité de requête que l'algorithme complexité requête optimale.

Existe-t-il des exemples de compromis entre le temps et la complexité des requêtes?

Existe-t-il des problèmes où l'algorithme de complexité temporelle le plus connu a une complexité de requête différente de celle de l'algorithme de complexité de requête le plus connu? En d'autres termes, pouvons-nous effectuer plus de requêtes pour faciliter les opérations entre requêtes?

Ou est-il un argument qui montre qu'il existe toujours une version d'un algorithme optimal asymptotiquement requête ayant une implémentation avec asymptotiquement meilleur temps complexité?

Voici une tentative de création d'une fonction artificielle avec la propriété suivante:

• Le problème peut être résolu avec requêtes, mais nécessite exp ( n ) temps.$O(\log n)$$\exp(n)$
• Le problème peut être résolu avec du temps , mais qui nécessite O ( n ) requêtes$O(n)$$O(n)$

Laissez la taille d'entrée soit . Laissez les premiers n bits de log (appelons cette chaîne x) coder l'entrée d'un problème complet pour EEXP. Les n bits suivants (appelons cette chaîne y) ont la propriété d'être tous nuls si et seulement si x est une instance NO du problème EEXP-complete.$n + \log n$$\log n$$n$

En d'autres termes, les premiers n bits de encodent un problème difficile, et les n bits suivants vous donnent un indice sur la solution du problème. Cependant, pour comprendre la solution en regardant la n chaîne de bits que vous faites Ohm ( n ) requêtes.$\log n$$n$$n$$\Omega(n)$

Ainsi, ce problème peut être résolu soit en lisant uniquement les n premiers bits et en passant du temps exp (n), soit en lisant n bits et en utilisant uniquement du temps linéaire.$\log n$$n$

La même fonction passe par la complexité de la requête quantique .. insérer des signes de racine carrée si nécessaire.

Une version plus extrême de l'exemple de Robin:

Soit la taille d'entrée , les n - 1 premiers bits (appelons cette chaîne x ) codant une machine de Turing T x . Correction d'une fonction f ( n ) . Soit le dernier bit de la chaîne 1 si la machine Turing T x s'arrête en moins de f ( n ) étapes. Le problème est alors de déterminer si T x s'arrête en moins de f ( n ) pas et que la parité de x est paire.$n$$n-1$$x$$T_x$$f(n)$$1$$T_x$$f(n)$$T_x$$f(n)$$x$

Ainsi, en faisant requêtes, le problème peut être résolu dans le temps O ( f ( n ) ) , tandis qu'en faisant n requêtes, le problème peut être résolu dans le temps O ( n ) .$n-1$$O(f(n))$$n$$O(n)$

J'aime la réponse de Robin Kothari et la modification de Joe Fitzsimons. Dans une extension évidente de leurs réponses, ils peuvent atteindre n'importe quel rapport de séparation (sauf constante vs non constante) entre la complexité de requête de plus en plus petite et la complexité de temps de plus en plus petite. Cependant, il n'existe aucun moyen évident de rendre leurs fonctions non partielles. Je veux souligner un problème naturel où nous avons une séparation et montrer que les grandes séparations sont plus difficiles pour les fonctions totales.

Un problème naturel

Ben Reichardt a signalé par e-mail le problème de l'évaluation des formules. La complexité de la requête quantique pour évaluer une formule AND-OR générale à lecture unique sur variables est Θ ( $n$. Cependant, leO($\Theta(\sqrt{n})$-l'algorithme de requête n'est pas efficace en temps. Ici, l'algorithme connu le plus rapide est montré pour faireO($O(\sqrt{n})$interroge et exécute dans le temps polylogarithmiquement pire. Nous avons donc un problème total naturel où il y a une séparation connue. Bien qu'il n'y ait aucune preuve que cette séparation doit exister.$O(\sqrt{n}\log{n})$

Les fonctions totales sont plus difficiles à séparer?

Pour moi, il semble qu'il soit plus difficile de trouver des fonctions totales avec des séparations prouvables. Pour montrer que le cas des fonctions totales et partielles est différent, je fournirai un argument sur la plus grande séparation entre les complexités des requêtes des algorithmes optimaux et optimaux pour une fonction totale.

En utilisant la borne inférieure de [1] de Simon, nous pouvons voir que si une fonction dépend de de ses variables, nous devrons en interroger au moins Ω ( log m ) . D'un autre côté, le plus que nous pourrions interroger est m . Notez qu'il n'y a aucune raison d'interroger toutes les n variables, car la sortie est indépendante de n - m d'entre elles (appelez ces bits morts) et pour une fonction totale aucune structure secrète ne sera révélée en regardant ces bits morts. Ainsi, même l'algorithme le plus optimal dans le temps pour une fonction totale peut être modifié pour utiliser au plus m requêtes en supposant simplement que les bits morts sont tous à 0 .$m$$\Omega{(\log m)}$$m$$n$$n - m$$m$$0$

Par conséquent, si nous écrivons , puis pour une fonction totale, étant donné l'algorithme optimal de requête avec complexité ( q 1 ( n ) , t 1 ( n ) ) , il existe un algorithme optimal temporel avec complexité ( q 2 ( n ) , t 2 ( n ) ) avec q 2 ( n ) ≤ f ( q 1 ( n ) ) et f ( 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))$ . En d'autres termes, nous ne pouvons pas avoir plus qu'une séparation exponentielle dans la complexité des requêtes entre les algorithmes optimaux pour les requêtes et optimaux dans le temps pour les fonctions totales. Je ne serais pas surpris si ces limites vraiment lâches pouvaient être améliorées.$f(n) = O(2^n)$

[1] HU Simon, "Un Z serré (loglogn) lié au temps pour les RAM parallèles pour calculer les fonctions booléennes non dégénérées", dans: Symp. on Foundations of Computation Theory, Notes de cours en informatique, Vol. 158, Springer, Berlin, 1983, p. 439–444.