Existe-t-il un problème non trivial dans la théorie des algorithmes en série avec une borne inférieure polynomiale non triviale de

Dans la théorie des algorithmes distribués, il y a des problèmes avec des bornes inférieures, comme , qui sont "grandes" (je veux dire, plus grandes que ), et non triviales. Je me demande s'il y a des problèmes avec des limites similaires dans la théorie de l'algorithme série, je veux dire d'ordre beaucoup plus grand que .$\Omega(n^2)$$\Omega(n\log n)$$\Omega(n\log n)$

Avec trivial, je veux dire "obtenu en considérant simplement que nous devons lire l'intégralité de l'entrée" et de même.

Il existe de tels problèmes par le théorème de la hiérarchie temporelle. Prenez tout problème qui est complet pour une classe de grande complexité. Par exemple, prenez un problème terminé pour$\mathsf{ExpTime}$. Un tel problème sera$\Omega(n^c)$ pour tous $c\in\mathbb{N}$.

Notez également que pour les problèmes $\mathsf{NP}$, il n'y a pas de limites inférieures de temps fortes dans le modèle TM à bandes multiples et l'existence d'algorithmes de temps linéaires pour SAT est cohérente avec l'état actuel des connaissances. (Dans le modèle TM à bande unique, il n'est pas difficile de montrer que de nombreux problèmes comme les palindromes$\Omega(n^2)$ mais ces limites inférieures dépendent essentiellement des particularités du modèle TM à bande unique.)

Certains problèmes simples qui ont des bornes inférieures supérieures à la taille de leurs entrées sont des algorithmes qui ont des tailles de sortie supérieures à leurs tailles d'entrée.

Quelques exemples:

• Le problème de l'énumération de toutes les solutions à 3-SAT, ou de façon similaire, le problème de l'énumération de tous les cycles hamiltoniens . Ces problèmes ont tous deux un nombre exponentiel de solutions dans le pire des cas. Ils ont donc une limite inférieure de$\Omega (c^n),c>1$. Fait intéressant cependant, le problème 3-SAT lui-même n'a pas de super-linéaire connu (supérieur à$\Omega (n)$) limites! Cela signifie que nous ne savons pas si c'est plus dur que linéaire!
• Vous pouvez même créer de nouveaux algorithmes comme celui-ci: "compléter un graphique" qui est, étant donné $G = V,E$, où $E=\varnothing$, et $n=|V|$, l'algorithme affichera un graphique $G' = V,E'$, où $E'=\left\{u,v|u\neq v\space\wedge\space u,v\in V \right\}$.

En outre, vous pourriez être en mesure de composer un problème qui a $\Omega (n^2)$sorties de taille moyenne, avec un problème qui prend $\Omega (n^2)$ comme entrée et sorties $\Omega (n)$ ou même $\Omega (1)$- sorties de taille (par exemple, quelque chose qui compte le nombre de sorties) pour obtenir un problème qui prend $\Omega(n)$-entrée et sorties de taille $\Omega (n)$-size sortie, et pourtant a un temps de fonctionnement supérieur à $\Omega (n)$. Cependant, il pourrait être très difficile de prouver (qu'il n'y a pas de raccourci pour obtenir la réponse en moins de temps).

Une autre façon dont certains problèmes ont connu des bornes inférieures est de restreindre le modèle de calcul.

Bien que la limite inférieure du tri de comparaison ne dépasse pas $\Omega (n\log n)$, Je pense qu'il vaut la peine d'en discuter. Le tri par comparaison est également un problème qui a une limite inférieure supérieure à sa taille d'entrée, mais sa limite inférieure ne dépasse pas$\Omega (n\log n)$, et en . Cependant, alors que je faisais des recherches, j'ai trouvé cette question sur mathoverflow: complexité temporelle super-linéaire bornes inférieures pour tout problème naturel dans NP . D'autres exemples énumérés dans la réponse sont bien ci-dessous$\Omega (n\log n)$. Je pense que l'essentiel est que si vous limitez le modèle de calcul, vous pouvez obtenir des limites inférieures pour les problèmes pour lesquels nous ne les avons pas autrement. Et si vous ne limitez pas le modèle de calcul, il est très difficile de prouver les limites inférieures des problèmes.