Go backward to 8 Feasible Basis ExtensionGo up to 2 Coordinate DescriptionsGo 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? |