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ù 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ù 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 mais pas  ;
  • le problème de décision d'une formule de la logique du premier ordre dans une structure automatique[2].

Références
  1. 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, , 244–253 p. (ISBN 0-89791-996-3, DOI 10.1145/275487.275515), « Complexity of Nonrecursive Logic Programs with Complex Values ».
  2. (en) Dietrich Kuske, « Theories of Automatic Structures and Their Complexity », dans Algebraic Informatics, Springer Berlin Heidelberg, (ISBN 9783642035630, DOI 10.1007/978-3-642-03564-7_5, lire en ligne), p. 81–98
  3. (en) Larry J. Stockmeyer, The Complexity of Decision Problems in Automata Theory and Logic, Massachusetts Institute of Technology, coll. « Ph.D. dissertation », (lire en ligne).
  4. (en) Leonid Libkin, « Logics for unranked trees : an overview », Logical Methods in Computer Science, vol. 2,‎ , p. 3:2, 31 (DOI 10.2168/LMCS-2(3:2)2006, Math Reviews 2295773, arXiv cs.LO/0606062).
  5. (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 », , 275–287 p. (DOI 10.1007/3-540-61511-3_91), « An improved lower bound for the elementary theories of trees ».
  6. (en) « Quine’s Fluted Fragment is Non-Elementary » [PDF].
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.