Algorithms and complexity for Turaev-Viro invariants

DOI10.1007/978-3-662-47672-7_23MaRDI QIDQ3448792zbMATH OpenOpenAlexFDO

Authors Clément Maria, Jonathan Spreer, Benjamin A. Burton

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.04099

Mathematics Subject Classification ID

Invariants of 3-manifolds (including skein modules, character varieties) (57K31) Triangulating manifolds (57Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Analysis of algorithms (68W40)

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 $rgeq3$. We resolve the question of complexity for $r=3$ and $r=4$, giving simple proofs that computing Turaev-Viro invariants for $r=3$ is polynomial time, but for $r=4$ is #P-hard. Moreover, we give an explicit fixed-parameter tractable algorithm for arbitrary $r$, 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

• 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
• scientific article; zbMATH DE number 4102053 (Why is no real title available?)
• scientific article; zbMATH DE number 2227021 (Why is no real title available?)
• Notes on Perelman's papers
• PP is as Hard as the Polynomial-Time Hierarchy
• State sum invariants of 3-manifolds and quantum \(6j\)-symbols
• STRUCTURES OF SMALL CLOSED NON-ORIENTABLE 3-MANIFOLD TRIANGULATIONS
• 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

(10)

• A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
• Treewidth, crushing and hyperbolic volume
• Algorithms and complexity for Turaev-Viro invariants
• A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number
• Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants
• scientific article; zbMATH DE number 7236450 (Why is no real title available?)
• The parameterized complexity of finding a 2-sphere in a simplicial complex
• Clarkson's algorithm for violator spaces
• Descriptive complexity of topological invariants
• Violator spaces: Structure and algorithms

Describes a project that uses

Uses Software

• ComputeTW
• Regina
• LibTW

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)