2025/03/04 by Bridges, Nicolas, Samperton, Eric · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Geometric Topology (math.GT) #Quantum Algebra (math.QA) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2503.02945
We show that for any fixed (2+1)-dimensional TQFT over ℂ of either Turaev-Viro-Barrett-Westbury or Reshetikhin-Turaev type, the problem of (exactly) computing its invariants on closed 3-manifolds is either solvable in polynomial time, or else it is #P-hard to (exactly) contract certain tensors that are built from the TQFT's fusion category. Our proof is an application of a dichotomy result of Cai and Chen [J. ACM, 2017] concerning weighted constraint satisfaction problems over ℂ. We leave for future work the issue of reinterpreting the conditions of Cai and Chen that distinguish between the two cases (i.e. #P-hard tensor contractions vs. polynomial time invariants) in terms of fusion categories. We expect that with more effort, our reduction can be improved so that one gets a dichotomy directly for TQFTs' invariants of 3-manifolds rather than more general tensors built from the TQFT's fusion category.