Determining whether a lattice is the face lattice of a polytope - NP hard or undecidable? According to this source (p. 10), determining whether a simplicial complex is a simplicial sphere (the sphere recognition problem) is undecidable.
According to this source, determining whether a lattice is the face lattice of a polytope (the Steinitz problem) is NP hard.
Given that the boundary of a simplicial polytope (encoded in the face lattice) is a simplicial sphere, which of the following is true:

*

*the second source is technically correct, but massively understating.

*the second source is actually assuming that the input lattice is already known to correspond to a simplicial sphere (as suggested by the phrasing of this question)

*sphere recognition is semi-decidable, i.e. the algorithm for detecting polytopal lattices can be used to correctly identify non-spherical complexes, but might fail on spherical ones.

*something special in the structure of polytopes makes it algorithmically possible to reject non-polytopal complexes that are still spheres (perhaps realizability of oriented matroids?)

Last option is that I am just misunderstanding something.
 A: There's no contradiction:

*

*I don't know the correct complexity, but I recall hearing several times that it is at least as hard as NP.


*It is not difficult to show (using Tarski's algorithm, as indicated in the comments) that recognition of polytopal face lattices is decidable. Given a face lattice, you need to check whether each vertex can be assigned a real coordinate vector such that the appropriate subsets of the vertex sets are precisely those that support faces of the convex hull. This is easy to state in the language of ordered fields. You don't need to assume that the lattice is the face lattice of a sphere for this algorithm to work.


*Sphere recognition is semi-decidable in the sense that there is a recognition algorithm that takes a simplicial complex, always halts if it is a sphere triangulation, and always returns the correct answer if it halts. It need not halt if the input is not a triangulated sphere.
This is because a simplicial complex is a triangulated sphere iff both the complex itself and each of the vertex links are simply connected homology spheres.


*This is correct, see part 2.
