backup

Go backward to 30 Steinitz Problem
Go up to 6 Realizability
XHTML 1.0

31 Simplicial Steinitz Problem

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.


backup Why are some symbols not displayed correctly?