|Output:||"Yes" if L is isomorphic to the face lattice of a simplicial polytope, "No" otherwise|
|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
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 ) 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.
|Related problems:||17, 30|