Go backward to 8 Feasible Basis Extension
Go up to 2 Coordinate Descriptions
Go forward to 10 Diameter

9 Recognizing Integer Polyhedra

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.