Théorie existentielle sur les réels

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 , pour laquelle des problèmes géométriques sur les graphes sont complets[3],[4].

Définition

modifier

Problèmes -complets

modifier

La classe   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  -dur si tout problème de   s'y réduit en temps polynomial. Un problème est  -complet s'il est dans   et s'il est  -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  -complet[5].

Notes et références

modifier
  1. (en) Algorithms in Real Algebraic Geometry, Berlin/New York, Springer Berlin Heidelberg, coll. « Algorithms and Computation in Mathematics », , 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,‎ , p. 460–467 (ISBN 0897912640, DOI 10.1145/62212.62257, lire en ligne, consulté le )
  3. (en) Marcus Schaefer, Graph Drawing, Springer Berlin Heidelberg, coll. « Lecture Notes in Computer Science », (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],‎ (lire en ligne, consulté le )
  5. (en) Marcus Schaefer, Thirty Essays on Geometric Graph Theory, Springer New York, (ISBN 978-1-4614-0109-4 et 9781461401100, DOI 10.1007/978-1-4614-0110-0_24, lire en ligne), p. 461–482