Name
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 parameterized by an integer \(r \ge 3\). We resolve the question of complexity for \(r=3\) and \(r=4\), giving simple proofs that the Turaev–Viro invariants for \(r=3\) can be computed in polynomial time, but computing the invariant for \(r=4\) is #P-hard. Moreover, we describe an algorithm for arbitrary r, which is fixed-parameter tractable with respect to the treewidth of the dual graph of the input triangulation. We show through concrete implementation and experimentation that this algorithm is practical—and indeed preferable—to the prior state of the art for real computation. The algorithm generalises to every triangulated 3-manifold invariant defined from tensor network contraction. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s41468-018-0016-2 | international colloquium on automata, languages and programming |
Keywords | Field | DocType |
Computational topology,3-manifolds,Invariants,#P-hardness,Parameterized complexity,57M27,57Q15,68Q17 | Integer,Discrete mathematics,Combinatorics,Parameterized complexity,Algorithm,Dual graph,Triangulation (social science),Real computation,Invariant (mathematics),Treewidth,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
2 | 1-2 | 2367-1734 |
Citations | PageRank | References |
3 | 0.48 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Benjamin A. Burton | 1 | 172 | 25.57 |
| Clément Maria | 2 | 40 | 5.29 |
| Jonathan Spreer | 3 | 47 | 11.46 |