Determining whether a lattice is the face lattice of a polytope - NP hard or undecidable?

Question

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.

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. — Sam Hopkins, Commented 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 — Benjamin Steinberg, Commented 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? — M. Winter, Commented 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 — Benjamin Steinberg, Commented 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. — Joshua Grochow, Commented Oct 18, 2022 at 3:50

Geva Yashfe · Accepted Answer · 2022-10-17 22:01:20Z

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.

1 Answer 1