Go backward to 2 Facet Enumeration Go up to 2 Coordinate Descriptions Go forward to 4 Polytope Containment XHTML 1.0

3 Polytope Verification

Input: Polytope P given in H-description, polytope Q given in V-description "Yes" if P = Q, "No" otherwise
Status (general): Open; polynomial time if P is simple or simplicial Polynomial time
 POLYTOPE VERIFICATION is strongly polynomially equivalent to Problem 1 and Problem 2 (see the comments there). POLYTOPE VERIFICATION is contained in coNP : we can prove Q ⊄ P by showing that some vertex of Q violates one of the inequalities describing P. If Q ⊂ P with Q ≠ P then there exists a point p of P  \ Q with "small" coordinates (e.g., some vertex of P not contained in Q) and a valid inequality for Q, which has "small" coefficients and is violated by p (e.g., an inequality defining a facet of Q that separates p from Q). However, it is unknown whether POLYTOPE VERIFICATION is in NP. Since it is easy to check whether Q ⊆ P, POLYTOPE VERIFICATION is Problem 4 restricted to the case that Q ⊆ P.