Est-il vraiment possible de prouver des limites inférieures?

Compte tenu de tout problème de calcul, la tâche de trouver des limites inférieures pour un tel calcul est-elle vraiment possible? Je suppose que cela se résume à la façon dont une seule étape de calcul est définie et quel modèle nous utilisons pour la preuve, mais étant donné que, prouvons-nous vraiment une borne inférieure alors en général? Ce que je veux dire, c'est que pouvons-nous prouver quelque chose comme "le problème ne peut pas être résolu plus rapidement que le temps " plutôt que "le problème peut être résolu en temps ou plus rapidement"?t ( X ) X t ( X $X$$t(X)$$X$$t(X)$

J'ai essayé de trouver des informations spécifiquement sur les bornes inférieures et des preuves de celles-ci, mais je ne trouve pas vraiment d'intérêt, des recommandations sur des livres / papiers / sites Web sur le sujet?

Nous pouvons absolument prouver de telles choses.

De nombreux problèmes ont des bornes inférieures triviales, comme celle de trouver le minimum d'un ensemble de nombres (qui ne sont pas triés / structurés de quelque manière que ce soit) prend au moins Ω ( n ) de temps. La preuve en est simple: un algorithme hypothétique qui s'exécute en temps o ( n ) ne peut pas examiner tous les nombres en entrée. Donc, si nous exécutions l'algorithme sur une entrée, nous pourrions observer qu'il n'a jamais examiné un élément particulier de l'entrée. En modifiant cet élément au minimum, nous pouvons faire échouer l'algorithme.$n$$\Omega(n)$$o(n)$

Une borne inférieure moins triviale est la borne inférieure pour le tri dans le modèle basé sur la comparaison. La preuve en est la suivante: étant donné une entrée de n nombres, il y a n ! sorties possibles (l'entrée peut être n'importe quelle permutation de la liste triée, donc la sortie peut également être n'importe quelle permutation de l'entrée). Si nous sommes limités à ne faire que des comparaisons, alors notre algorithme (en moyenne) doit effectuer au moins log 2 ( n ! ) = Ω ( n log n ) comparaisons afin de pouvoir donner $\Omega(n \log n)$$n$$n!$$\log_2(n!)=\Omega(n \log n)$différentes sorties.$n!$

Les limites inférieures peuvent être encore plus fortes. Il existe plusieurs problèmes (notamment les problèmes -hard) pour lesquels il existe une borne inférieure exponentielle. Les problèmes de cette classe incluent le calcul de stratégies optimales pour des jeux tels que les échecs (généralisés), les dames et le go. La preuve en est fournie par le théorème de la hiérarchie temporelle , qui stipule (sous réserve de certaines restrictions sur f ):$EXPTIME$$f$

Étant donné une fonction , il existe un problème de calcul qui peut être résolu dans le temps O ( f ( n ) ) mais ne peut pas être résolu dans le temps o ( f ( n $f$$O(f(n))$.$o(\frac{f(n)}{\log n})$

Donc, fondamentalement, si vous pouvez penser à une fonction il existe un problème qui nécessite autant de temps pour être résolu.$f$

Enfin, une autre possibilité de ne pas nécessairement prouver une limite inférieure de temps mais quelque chose de plus fort encore montre l'indécidabilité d'un problème (par exemple l'arrêt, la correspondance).

Oui c'est possible. L'exemple classique est le fait que tout algorithme de tri basé sur la comparaison nécessite des comparaisons pour trier une liste de longueur n .$\Omega(n\log n)$$n$

Cependant, les limites inférieures semblent être beaucoup plus difficiles à prouver que les limites supérieures. Pour prouver qu'il existe un algorithme de tri qui nécessite des comparaisons , il vous suffit de présenter un tel algorithme (merge sort - voila !). Mais pour une borne inférieure, vous devez en quelque sorte montrer qu'aucun algorithme dans une classe particulière ne peut résoudre votre problème. La difficulté de le faire est illustrée par le fait que nous savons seulement que L ⊆ N L ⊆ P ⊆ N P ⊆ P S P A C $O(n\log n)$ même si nous savons qu'au moins une de ces inclusions est stricte ( L ⊂ P S P A C E par le théorème de la hiérarchie spatiale) et la plupart des gens pensent qu'elles sonttoutesstrictes.

D'un autre côté, Ryan Williams a un bon article (et un discours, que j'ai entendu plusieurs fois) intitulé Algorithms for Circuits et Circuits for Algorithms , dans lequel il soutient que trouver des limites inférieures et trouver des algorithmes ne sont pas fondamentalement tous si différent. Par exemple, il cite la preuve de l'indécidabilité du problème d'arrêt comme exemple d'un algorithme (la machine universelle de Turing) utilisé exactement pour prouver une borne inférieure (indécidabilité).

$n$

Cependant, il y a un point dans la question qui appelle quelques remarques supplémentaires concernant la borne inférieure (ou les bornes de complexité en général).

En fait, le choix de ce qui est une seule étape de calcul n'est pas pertinent, tant que les étapes de calcul peuvent être considérées comme ayant une limite supérieure (et une limite inférieure) constante. Le résultat de la complexité sera le même puisqu'il est défini jusqu'à une constante. Prendre 3 comparaisons comme opérations unitaires, ou seulement une seule, ne fait aucune différence.

Il en va de même pour la taille des données qui sert de référence pour évaluer le coût du calcul. Prendre un seul entier ou deux entiers comme unité de taille ne fait aucune différence.

Cependant, les deux choix doivent être liés.

$n$$\log n$$O(\log n)$

La question de savoir si une opération peut être considérée comme ayant un coût unitaire est étroitement liée aux données qui peuvent être considérées comme ayant une taille unitaire. Et cela dépend du niveau d'abstraction que vous choisissez pour votre modèle de calcul.