Go up to 6 Realizability
Go forward to 31 Simplicial Steinitz Problem
|
Go up to 6 Realizability Go 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 d ≤ 2. Steinitz's Theorem allows to solve d=3 in polynomial time: construct the (abstract) graph G, test if the facets can consistently be embedded in the plane (linear time [30][45]) and check for 3-connectedness (in linear time, see Hopcroft and Tarjan [29]). Mnëv proved that the Steinitz Problem for d-polytopes with d+4 vertices is NP-hard [47]. Even more, Richter-Gebert [55] proved that for (fixed) d ≥ 4 the problem is NP-hard. For fixed d ≥ 4 it is neither known whether the problem is in NP nor whether it is in coNP . It seems unlikely to be in NP, since there are 4-polytopes which cannot be realized with rational coordinates of coding length which is bounded by a polynomial in | L | (see Richter-Gebert [55]). |
| Related problems: | 31 |
|---|
|
|
Why are some symbols not displayed correctly? |