Des problèmes pour lesquels il a été démontré qu’il n’existera jamais d’algorithmes dont il est garanti qu’ils finissent en un temps raisonnable. Pour certains type de problème, on ne sait pas encore.Re Ebion,
Comme par example?
Il y a une sorte de hiérarchie de la complexité : les classes de complexité de calcul. Ces classes distinguent deux aspects : le temps de calcul en fonction de la taille du problème (le nombre d’éléments composant le problème ou la valeur d’un nombre) et le déterminisme (déterministe ou non‑déterministe). Ça va du plus simple, l’algorithme déterministe en temps constant, au pire du pire, comme l’algorithme non‑déterministe dont le temps de calcul augmente avec l’exponentiel de la taille du problème quand il y arrive. Entre les deux, il y a les algorithmes déterministes qui calculent en un temps logarithmiques (l’idéal en informatique) ou en un temps linéaire (pas l’idéal, mais acceptable). Pour le pire du pire, qui augmente avec l’exponentiel de la taille du problème, il n’y a pas d’autres moyens que d’utiliser des solutions empiriques ou par essai‑erreur, comme le disait Ébion, excepté si la taille est toute petite.
Je ne connais pas de site simple sur la question (c’est une question compliquée