Go backward to 8 Feasible Basis Extension
Go up to 2 Coordinate Descriptions
Go forward to 10 Diameter
|
Go backward to 8 Feasible Basis Extension Go up to 2 Coordinate Descriptions Go forward to 10 Diameter |
XHTML 1.0 |
| Input: | Polytope P in H-description |
|---|---|
| Output: | "Yes" if P has only integer vertices, "No" otherwise |
| Status (general): | Strongly coNP -complete |
|---|---|
| Status (fixed dim.): | Polynomial time |
| The hardness-proof is by Papadimitriou and Yannakakis [52]. For fixed dimension, one can enumerate all vertices (Problem 1) and check whether they are integral in polynomial time. |
|
|
Why are some symbols not displayed correctly? |