Go up to 6 RealizabilityGo forward to 31 Simplicial Steinitz Problem |
XHTML 1.0 |

Input: | Lattice L |
---|---|

Output: | "Yes" if L is isomorphic to the face lattice of a
polytope, "No" otherwise |

Status (general): | NP-hard |
---|---|

Status (fixed dim.): | NP-hard |

If L is isomorphic to the face lattice of a polytope,
it is ranked, atomic, and coatomic. These properties can be tested
in polynomial time in the size of L. Furthermore, in
this case, the dimension d of a candidate polytope has to be
rank L-1.
The problem is trivial for dimension Mnëv proved that the Steinitz Problem for For fixed |

Related problems: | 31 |
---|

Why are some symbols not displayed correctly? |