Algorithms and complexity for Turaev–Viro invariants
Algorithms and complexity for Turaev–Viro invariants
复制标题
Turaev-Viro 不变量的算法和复杂性
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Spreer
中科院分区：
文献类型：
--
作者：
Benjamin A. Burton;Clément Maria;J. Spreer
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≥3documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$r ge 3$$end{document}. We resolve the question of complexity for r=3documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$r=3$$end{document} and r=4documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$r=4$$end{document}, giving simple proofs that the Turaev–Viro invariants for r=3documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$r=3$$end{document} can be computed in polynomial time, but computing the invariant for r=4documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$r=4$$end{document} 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.
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≥3documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$r ge 3$$end{document}. We resolve the question of complexity for r=3documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$r=3$$end{document} and r=4documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$r=4$$end{document}, giving simple proofs that the Turaev–Viro invariants for r=3documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$r=3$$end{document} can be computed in polynomial time, but computing the invariant for r=4documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$r=4$$end{document} 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.