Théorie existentielle sur les réels

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