On sait qu’un polyèdre convexe borné peut s’exprimer aussi bien comme l’enveloppe convexe V d’une famille de points que comme l’intersection H d’une famille finie de demi-espaces. On peut donc vouloir vérifier que deux telles représentations sont équivalentes.

On montre facilement que ce problème est dans co-NP :

  1. L’inclusion V ⊆ H se vérifie aisément (produit de matrices).

  2. H ⊊ V si et seulement si il existe un sommet de H (choix non déterministe sur les contraintes à intersecter) qui sort de V (test par programmation linéaire sur les coordonnées barycentriques).

Apparemment, la complexité de ce problème est inconnue ! Pas d’algorithme polynomial connu, pas de preuve de complétude…

PS L'algorithme suivant (pour polyèdres bornés) ne fonctionne pas :

  1. On minimise les représentations sommets et contraintes (un appel de programmation linéaire pour chaque sommet ou contrainte par rapport aux autres, soit temps polynomial).
  2. On vérifie l'inclusion des sommets dans les contraintes (produit de matrices).
  3. On vérifie que chaque contrainte sature au moins d sommets et chaque sommet au moins d contraintes et qu'aucune contrainte (resp. sommet) ne sature un sur-ensemble des sommets (resp. contraintes) saturés par une autre contrainte (resp. sommet).
En effet, la condition 3. est validée par un cube dont on a ôté un des sommets de la liste des générateurs.