up forward

Go up to 6 Realizability
Go forward to 31 Simplicial Steinitz Problem
XHTML 1.0

30 Steinitz Problem

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]).


up forward Why are some symbols not displayed correctly?