| Input: | Polytope P given in H-description, polytope Q given in V-description |
|---|---|
| Output: | "Yes" if P Í Q, "No" otherwise |
| Status (general): | coNP-complete |
|---|---|
| Status (fixed dim.): | Polynomial time |
| Freund and Orlin [20] proved that this problem is coNP-complete. Note that the reverse question whether Q Í P is trivial. The questions where either both P and Q are given in H-description or both in V-description can be solved by linear programming (Problem 25), see Eaves and Freund [17]. For fixed dimension, one can enumerate all vertices of P in polynomial time (see Problem 1) and compare the descriptions of P and Q (after removing redundant points). |
| Related problems: | 3 |
|---|