« Problème non élémentaire » : différence entre les versions

Un article de Wikipédia, l'encyclopédie libre.
Navigation interactive dans l’historique
← Modification précédenteModification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
Fschwarzentruber (discuter | contributions)
8 059 modifications
Aucun résumé des modifications
Fschwarzentruber (discuter | contributions)
8 059 modifications
Aucun résumé des modifications
Ligne 1 : Ligne 1 :
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 Nonrecursive Logic Programs with Complex Values|doi=10.1145/275487.275515|isbn=0-89791-996-3|location=New York, NY, USA|pages=244–253|publisher=ACM|title=Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '98)|year=1998}}.</ref>''' est un [[problème de décision]] qui n'est pas dans [[ELEMENTARY (complexité)|ELEMENTARY]].
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 Nonrecursive Logic Programs with Complex Values|doi=10.1145/275487.275515|isbn=0-89791-996-3|location=New York, NY, USA|pages=244–253|publisher=ACM|title=Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '98)|year=1998}}.</ref>''' est un [[problème de décision]] qui n'est pas dans [[ELEMENTARY (complexité)|ELEMENTARY]]. Pour montrer qu'un problème est non élémentaire, on montre qu'il est k-EXPTIME pour tout entier k<ref name=":0">{{Chapitre|langue=en|prénom1=Dietrich|nom1=Kuske|titre chapitre=Theories of Automatic Structures and Their Complexity|titre ouvrage=Algebraic Informatics|éditeur=Springer Berlin Heidelberg|date=2009|isbn=9783642035630|doi=10.1007/978-3-642-03564-7_5|lire en ligne=https://link.springer.com/chapter/10.1007/978-3-642-03564-7_5|consulté le=2018-10-10|passage=81–98}}</ref>.


Voici quelques exemples de problèmes non élémentaires et décidables :
Voici quelques exemples de problèmes non élémentaires et décidables :
Ligne 7 : Ligne 7 :
* le problème de décision pour l'[[algèbre des termes]]<ref>{{citation|last=Vorobyov|first=Sergei|contribution=An improved lower bound for the elementary theories of trees|doi=10.1007/3-540-61511-3_91|pages=275–287|publisher=Springer|series=Lecture Notes in Computer Science|title=Automated Deduction — Cade-13: 13th International Conference on Automated Deduction New Brunswick, NJ, USA, July 30 – August 3, 1996, Proceedings|volume=1104|year=1996}}.</ref>
* le problème de décision pour l'[[algèbre des termes]]<ref>{{citation|last=Vorobyov|first=Sergei|contribution=An improved lower bound for the elementary theories of trees|doi=10.1007/3-540-61511-3_91|pages=275–287|publisher=Springer|series=Lecture Notes in Computer Science|title=Automated Deduction — Cade-13: 13th International Conference on Automated Deduction New Brunswick, NJ, USA, July 30 – August 3, 1996, Proceedings|volume=1104|year=1996}}.</ref>
* le problème de satisfiabilité du "Quine's fluted fragment" de la [[logique du premier ordre]]<ref>{{Cite web|url=http://drops.dagstuhl.de/opus/volltexte/2016/6579/pdf/LIPIcs-CSL-2016-39.pdf|title=Quine’s Fluted Fragment is Non-Elementary|last=|first=|date=|website=|archive-url=|archive-date=|dead-url=|access-date=}}</ref>. 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 <math>\exists x \forall y p(x, y)</math>mais pas <math>\exists x \forall y p(y, x)</math>.
* le problème de satisfiabilité du "Quine's fluted fragment" de la [[logique du premier ordre]]<ref>{{Cite web|url=http://drops.dagstuhl.de/opus/volltexte/2016/6579/pdf/LIPIcs-CSL-2016-39.pdf|title=Quine’s Fluted Fragment is Non-Elementary|last=|first=|date=|website=|archive-url=|archive-date=|dead-url=|access-date=}}</ref>. 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 <math>\exists x \forall y p(x, y)</math>mais pas <math>\exists x \forall y p(y, x)</math>.
*le problème de décision d'une formule de la logique du premier ordre dans une [[structure automatique]].
*le problème de décision d'une formule de la logique du premier ordre dans une [[structure automatique]]<ref name=":0" />.

Version du 10 octobre 2018 à 15:28

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. Pour montrer qu'un problème est non élémentaire, on montre qu'il est k-EXPTIME pour tout entier k[2].

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].
  1. ↑ « {{{1}}} ».
  2. ↑ a et b (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. ↑ « {{{1}}} »
  4. ↑ « {{{1}}} ».
  5. ↑ « {{{1}}} ».
  6. ↑ « Quine’s Fluted Fragment is Non-Elementary »
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Problème_non_élémentaire&oldid=152915324 ».