AProPo -- 30 Steinitz Problem

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

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