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 $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 $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[3] ;
le problème de décision d'une formule de la logique monadique du second-ordre sur les arbres[4] ;
le problème de décision pour l'algèbre des termes[5] ;
le problème de satisfiabilité du « Quine's fluted fragment » de la logique du premier ordre[6]. 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[2].

Références

Sergei Vorobyov et Andrie Voronkov, Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '98), New York, NY, USA, ACM, 1998, 244–253 p. (ISBN 0-89791-996-3, DOI 10.1145/275487.275515), « Complexity of Nonrecursive Logic Programs with Complex Values ».
(en) Dietrich Kuske, « Theories of Automatic Structures and Their Complexity », dans Algebraic Informatics, Springer Berlin Heidelberg, 2009 (ISBN 9783642035630, DOI 10.1007/978-3-642-03564-7_5, lire en ligne), p. 81–98
(en) Larry J. Stockmeyer, The Complexity of Decision Problems in Automata Theory and Logic, Massachusetts Institute of Technology, coll. « Ph.D. dissertation », 1974 (lire en ligne).
(en) Leonid Libkin, « Logics for unranked trees : an overview », Logical Methods in Computer Science, vol. 2,‎ 2006, p. 3:2, 31 (DOI 10.2168/LMCS-2(3:2)2006, MR 2295773, arXiv cs.LO/0606062).
(en) Sergei Vorobyov, Automated Deduction — Cade-13 : 13th International Conference on Automated Deduction New Brunswick, NJ, USA, July 30 – August 3, 1996, Proceedings, vol. 1104, Springer, coll. « Lecture Notes in Computer Science », 1996, 275–287 p. (DOI 10.1007/3-540-61511-3_91), « An improved lower bound for the elementary theories of trees ».
(en) « Quine’s Fluted Fragment is Non-Elementary » [PDF].

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.