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.

does notmean that the problem is (known to be) in NP. $\endgroup$4more comments