backup forward

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
Output: "Yes" if P = Q, "No" otherwise
Status (general): Open; polynomial time if P is simple or simplicial
Status (fixed dim.): 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.


backup forward Why are some symbols not displayed correctly?