Problème non élémentaire

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(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 : c'est-à-dire qu'il est plus dur que tout problème décidable en temps $O(2^{2^{{\text{⋰ }}^{2^{n}}}})$ où le nombre de 2 dans la tour d'exponentielles est k.

Exemples

Voici quelques exemples de problèmes non élémentaires et décidables :

• le problème d'équivalence d'expression rationnelle avec complémentation ;
• le problème de décision d'une formule de la logique monadique du second-ordre sur les arbres ;
• le problème de décision pour l'algèbre des termes ;
• le problème de satisfiabilité du « Quine's fluted fragment » de la logique du premier ordre. Il s'agit du fragment où les variables apparaissent dans un prédicat dans le même ordre qu'elles sont quantifiées. On peut écrire $\exists x\forall y\ p(x,y)$mais pas $\exists x\forall y\ p(y,x)$ ;
• le problème de décision d'une formule de la logique du premier ordre dans une structure automatique.