Go backward to 30 Steinitz Problem
Go up to 6 Realizability
|
Go backward to 30 Steinitz Problem Go up to 6 Realizability |
XHTML 1.0 |
| Input: | Lattice L |
|---|---|
| Output: | "Yes" if L is isomorphic to the face lattice of a simplicial polytope, "No" otherwise |
| Status (general): | NP-hard |
|---|---|
| Status (fixed dim.): | Open |
|
As for Problem 30, L is
ranked, atomic, and coatomic if the answer is "Yes." In this
case, the dimension d of any matched polytope is
rank L-1.
As for general polytopes (Problem 30), this problem is polynomial time solvable in dimension d ≤ 3. The problem is NP-hard, which follows from the above mentioned fact that the Steinitz problem for d-polytopes with d+4 vertices is NP-hard and a construction (Bokowski and Sturmfels [7]) which generalizes it to the simplicial case (but increases the dimension). It is, however, open whether the problem is NP-hard for fixed dimension. For fixed d ≥ 4, it is neither known whether the problem is in NP nor whether it is in coNP . The following question is interesting in connection with Problem 17 (see also the notes there): Given an (abstract) graph G, is G the graph of a simple polytope? If we do not restrict the question to simple polytopes the problem is also interesting. |
| Related problems: | 17, 30 |
|---|
|
|
Why are some symbols not displayed correctly? |