Kirby Problem 3.27

Definitions and mathematical statement

Encode a compact connected orientable three-manifold by a finite triangulation, specified by tetrahedra and simplicial face-identification data, including unglued boundary faces. Input size is the length of this finite description; with $t$ tetrahedra it is $O(t\log(t+2))$ in a standard indexed encoding. Inputs are promised to triangulate manifolds in the stated class.

The homeomorphism decision problem takes two such triangulations and asks whether their underlying manifolds are homeomorphic. No orientation-preserving condition is imposed unless it is separately specified. Determine its computational complexity by substantially improving the known gap between upper and lower bounds.

For a fixed compact orientable three-manifold $N$, the recognition problem has one variable input $M$ and asks whether $M\cong N$. Determine its complexity as a function of the triangulation size of $M$. In particular, is recognition of $S^3$ possible by a deterministic polynomial-time algorithm? The polynomial exponent must be independent of the input triangulation.

These questions seek complexity bounds, not merely termination of a homeomorphism algorithm. Allowing both $M$ and $N$ to vary is a different problem from recognizing one fixed $N$; an efficient algorithm for one recognition problem need not settle the two-input problem.

Short English statement

Determine the complexity of three-manifold homeomorphism and recognition, especially whether the three-sphere can be recognized in polynomial time.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 2825 (KP-3.27), Kirby's Problems in Low-Dimensional Topology. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 K3: A New Problem List in Low-Dimensional Topology, Problem 3.27. Expanded formulation of the supplied catalogue statement. https://math.berkeley.edu/sites/default/files/surv-295-ruberman-watermarked-author-pdf.pdf.