Algorithms and complexity for Turaev-Viro invariants
From MaRDI portal
Publication:3448792
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Triangulating manifolds (57Q15) Parameterized complexity, tractability and kernelization (68Q27) Invariants of 3-manifolds (including skein modules, character varieties) (57K31)
Abstract: The Turaev-Viro invariants are a powerful family of topological invariants for distinguishing between different 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them require exponential time. The invariants are parameterised by an integer . We resolve the question of complexity for and , giving simple proofs that computing Turaev-Viro invariants for is polynomial time, but for is #P-hard. Moreover, we give an explicit fixed-parameter tractable algorithm for arbitrary , and show through concrete implementation and experimentation that this algorithm is practical---and indeed preferable---to the prior state of the art for real computation.
Recommendations
- Algorithms and complexity for Turaev-Viro invariants
- Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants
- A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
- A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number
- Computing Turaev-Viro invariants for 3-manifolds
Cites work
- scientific article; zbMATH DE number 4102053 (Why is no real title available?)
- scientific article; zbMATH DE number 2227021 (Why is no real title available?)
- Algorithmic topology and classification of 3-manifolds
- Computing Turaev-Viro invariants for 3-manifolds
- Courcelle's theorem for triangulations
- Detecting genus in vertex links for the fast enumeration of \(3\)-manifold triangulations
- Graph minors. II. Algorithmic aspects of tree-width
- Notes on Perelman's papers
- PP is as Hard as the Polynomial-Time Hierarchy
- STRUCTURES OF SMALL CLOSED NON-ORIENTABLE 3-MANIFOLD TRIANGULATIONS
- State sum invariants of 3-manifolds and quantum \(6j\)-symbols
- Symmetries, Isometries and Length Spectra of Closed Hyperbolic Three-Manifolds
- The 3-manifold invariants of Witten and Reshetikhin-Turaev for sl\((2,\mathbb{C})\)
- The complexity of computing the permanent
- Treewidth computations. I: Upper bounds
- Treewidth. Computations and approximations
Cited in
(9)- Violator spaces: Structure and algorithms
- Algorithms and complexity for Turaev-Viro invariants
- A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number
- Clarkson's algorithm for violator spaces
- Treewidth, crushing and hyperbolic volume
- Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants
- A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
- The parameterized complexity of finding a 2-sphere in a simplicial complex
- scientific article; zbMATH DE number 7236450 (Why is no real title available?)
This page was built for publication: Algorithms and complexity for Turaev-Viro invariants
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448792)