2015 | OriginalPaper | Buchkapitel
Algorithms and Complexity for Turaev-Viro Invariants
verfasst von : Benjamin A. Burton, Clément Maria, Jonathan Spreer
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$$r \ge 3$$
r
≥
3
. We resolve the question of complexity for
$$r=3$$
r
=
3
and
$$r=4$$
r
=
4
, giving simple proofs that computing Turaev-Viro invariants for
$$r=3$$
r
=
3
is polynomial time, but for
$$r=4$$
r
=
4
is #P-hard. Moreover, we give an explicit fixed-parameter tractable algorithm for arbitrary
$$r$$
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.