En théorie de la complexité, un problème non élémentaire 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 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 : c'est-à-dire qu'il est plus dur que tout problème décidable en temps où le nombre de 2 dans la tour d'exponentielles est k.