« Problème non élémentaire » : différence entre les versions
Contenu supprimé Contenu ajouté
Nouvelle page : En théorie de la complexité, un '''problème non élémentaire<ref>{{citation|last1=Vorobyov|first1=Sergei|last2=Voronkov|first2=Andrie|contribution=Complexity of Nonrecursi... |
(Aucune différence)
|
Version du 10 octobre 2018 à 14:26
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 ELEMENTARY.
Voici quelques exemples de problèmes non élémentaires et décidables :
- le problème d'équivalence d'expression rationnelle avec complémentation[2]
- le problème de décision d'une formule de la logique du second-ordre monadique sur les arbres[3]
- le problème de décision pour l'algèbre des termes[4]
- le problème de satisfiabilité du "Quine's fluted fragment" de la logique du premier ordre[5]
- « {{{1}}} ».
- « {{{1}}} »
- « {{{1}}} ».
- « {{{1}}} ».
- « Quine’s Fluted Fragment is Non-Elementary »