Quantum topology provides various frameworks for defining and computing invariants of manifolds. One such framework of substantial interest in both mathematics and physics is the Turaev-Viro-Barrett-Westbury state sum construction, which uses the data of a spherical fusion category to define topological invariants of triangulated 3-manifolds via tensor network contractions. In this work we consider a restricted class of state sum invariants of 3-manifolds derived from Tambara-Yamagami categories. These categories are particularly simple, being entirely specified by three pieces of data: a finite abelian group, a bicharacter of that group, and a sign $\pm 1$. Despite being one of the simplest sources of state sum invariants, the computational complexities of Tambara-Yamagami invariants are yet to be fully understood. We make substantial progress on this problem. Our main result is the existence of a general fixed parameter tractable algorithm for all such topological invariants, where the parameter is the first Betti number of the 3-manifold with $\mathbb{Z}/2\mathbb{Z}$ coefficients. We also explain that these invariants are sometimes #P-hard to compute (and we expect that this is almost always the case). Contrary to other domains of computational topology, such as graphs on surfaces, very few hard problems in 3-manifold topology are known to admit FPT algorithms with a topological parameter. However, such algorithms are of particular interest as their complexity depends only polynomially on the combinatorial representation of the input, regardless of size or combinatorial width. Additionally, in the case of Betti numbers, the parameter itself is easily computable in polynomial time.
翻译:暂无翻译