# 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:

1. the second source is technically correct, but massively understating.
2. 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)
3. 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.
4. 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.

• Quoting your second link: "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 [55])." Note that NP hard does not mean that the problem is (known to be) in NP. Oct 17, 2022 at 17:35
• Maybe the main theorem of ams.org/journals/bull/1987-17-01/S0273-0979-1987-15532-7/… is helpful? It seems to say that decidability is equivalent to the rational version of Hilbert's 10 Oct 17, 2022 at 18:06
• @Sam But if it were indeed known to be undecidable then we would know that it is neither in NP nor coNP, right? Oct 17, 2022 at 18:37
• I don't think it is a contradiction. It may be known to be at least NP hard and potentially undecidable Oct 17, 2022 at 19:50
• FYI while Tarski is much closer to NP than undecidable, the best known upper bound is PSPACE, which I generally think of as pretty far from NP. Oct 18, 2022 at 3:50