|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|