|Output:||"Yes" if L is isomorphic to the face lattice of a polytope, "No" otherwise|
|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
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 ) and check for 3-connectedness (in linear time, see Hopcroft and Tarjan ).
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 ).