Théorie existentielle sur les réels

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources (octobre 2016).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

En logique mathématique, la théorie existentielle sur les réels est l'ensemble des formules existentielles de la logique premier ordre vraies sur les réels^[1]. Elle est intéressante pour la planification de mouvement de robots. Elle est décidable et NP-dure et dans PSPACE^[2]. Elle définit aussi une classe de complexité entre NP et PSPACE, notée $\exists \mathbb {R}$ , pour laquelle des problèmes géométriques sur les graphes sont complets^[3]^,^[4].

Définition[modifier | modifier le code]

Problèmes $\exists \mathbb {R}$ -complets[modifier | modifier le code]

La classe $\exists \mathbb {R}$ est la classe des problèmes de décision qui se réduisent en temps polynomial à vérifier si une formule de la théorie existentielle sur les réels est vraie. Un problème est $\exists \mathbb {R}$ -dur si tout problème de $\exists \mathbb {R}$ s'y réduit en temps polynomial. Un problème est $\exists \mathbb {R}$ -complet s'il est dans $\exists \mathbb {R}$ et s'il est $\exists \mathbb {R}$ -dur.

Le problème de savoir si un graphe non orienté peut être dessiné dans le plan en représentant les arêtes par des lignes droites de longueur 1 est $\exists \mathbb {R}$ -complet^[5].

Notes et références[modifier | modifier le code]

↑ (en) Algorithms in Real Algebraic Geometry, Berlin/New York, Springer Berlin Heidelberg, coll. « Algorithms and Computation in Mathematics », 1^er janvier 2006, 662 p. (ISBN 978-3-540-33098-1 et 9783540330998, DOI 10.1007/3-540-33099-2_14, lire en ligne), p. 505–532
↑ John Canny, « Some Algebraic and Geometric Computations in PSPACE », Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, ACM, sTOC '88,‎ 1^er janvier 1988, p. 460–467 (ISBN 0897912640, DOI 10.1145/62212.62257, lire en ligne, consulté le 18 octobre 2016)
↑ (en) Marcus Schaefer, Graph Drawing, Springer Berlin Heidelberg, coll. « Lecture Notes in Computer Science », 22 septembre 2009 (ISBN 978-3-642-11804-3 et 9783642118050, DOI 10.1007/978-3-642-11805-0_32, lire en ligne), p. 334–344
↑ Jiri Matousek, « Intersection graphs of segments and $\exists\mathbb{R}$ », arXiv:1406.2636 [cs, math],‎ 10 juin 2014 (lire en ligne, consulté le 18 octobre 2016)
↑ (en) Marcus Schaefer, Thirty Essays on Geometric Graph Theory, Springer New York, 1^er janvier 2013 (ISBN 978-1-4614-0109-4 et 9781461401100, DOI 10.1007/978-1-4614-0110-0_24, lire en ligne), p. 461–482

Portail des mathématiques

[1] (en) Algorithms in Real Algebraic Geometry, Berlin/New York, Springer Berlin Heidelberg, coll. « Algorithms and Computation in Mathematics », 1^er janvier 2006, 662 p. (ISBN 978-3-540-33098-1 et 9783540330998, DOI 10.1007/3-540-33099-2_14, lire en ligne), p. 505–532

[2] John Canny, « Some Algebraic and Geometric Computations in PSPACE », Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, ACM, sTOC '88,‎ 1^er janvier 1988, p. 460–467 (ISBN 0897912640, DOI 10.1145/62212.62257, lire en ligne, consulté le 18 octobre 2016)

[3] (en) Marcus Schaefer, Graph Drawing, Springer Berlin Heidelberg, coll. « Lecture Notes in Computer Science », 22 septembre 2009 (ISBN 978-3-642-11804-3 et 9783642118050, DOI 10.1007/978-3-642-11805-0_32, lire en ligne), p. 334–344

[4] Jiri Matousek, « Intersection graphs of segments and $\exists\mathbb{R}$ », arXiv:1406.2636 [cs, math],‎ 10 juin 2014 (lire en ligne, consulté le 18 octobre 2016)

[5] (en) Marcus Schaefer, Thirty Essays on Geometric Graph Theory, Springer New York, 1^er janvier 2013 (ISBN 978-1-4614-0109-4 et 9781461401100, DOI 10.1007/978-1-4614-0110-0_24, lire en ligne), p. 461–482

[1]

[2]

[3]

[4]

[5]

Définition[modifier | modifier le code]

Problèmes ∃ R {\displaystyle \exists \mathbb {R} } -complets[modifier | modifier le code]

Notes et références[modifier | modifier le code]

Problèmes $\exists \mathbb {R}$ -complets[modifier | modifier le code]