| 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. |
| Related problems: | 1, 2, 4 |
|---|