Je viens de trouver cette phrase à la page 6 de "Ordinateurs et intractabilité" de Garey et Johnson.
Tout algorithme dont la fonction de complexité temporelle ne peut pas être ainsi bornée est appelé algorithme de temps exponentiel (bien qu'il convient de noter que cette définition inclut certaines fonctions de complexité temporelle non polynomiales, comme , qui ne sont normalement pas considérées comme exponentielles les fonctions).
Ma question comme suit,
Si n'est pas polynomial ni exponentiel, alors comment s'appelle cette fonction? Est-ce que cela a un nom ou des cas spéciaux ou non?
Je vous remercie.