Go backward to 2 Facet Enumeration
Go up to 2 Coordinate Descriptions
Go forward to 4 Polytope Containment
|
Go backward to 2 Facet Enumeration Go up to 2 Coordinate Descriptions Go forward to 4 Polytope Containment |
XHTML 1.0 |
| 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 |
|---|
|
|
Why are some symbols not displayed correctly? |