Problème non élémentaire

En théorie de la complexité, un problème non élémentaire^[1] est un problème de décision qui n'est pas dans la classe ELEMENTARY. En d'autres termes, un problème est non élémentaire s'il n'existe pas d'algorithmes qui le décident en temps ${\displaystyle O(2^{2^{{\text{⋰ }}^{2^{n}}}})}$ où n est la taille de l'instance à traiter, et le nombre de 2 dans la tour d'exponentielles est fixé. Pour montrer qu'un problème est non élémentaire, on peut démontrer qu'il est k-EXPTIME-difficile pour tout entier k^[2] : c'est-à-dire qu'il est plus dur que tout problème décidable en temps ${\displaystyle O(2^{2^{{\text{⋰ }}^{2^{n}}}})}$ où le nombre de 2 dans la tour d'exponentielles est k.