AProPo -- 31 Simplicial Steinitz Problem

Go backward to 30 Steinitz Problem
Go up to 6 Realizability

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.