Towards a complexity-theoretic dichotomy for TQFT invariants
Nicolas Bridges (Purdue) and Eric Samperton (Purdue)
我们证明，对于任意固定的(2+1)维复TQFT（无论是Turaev-Viro-Barrett-Westbury型还是Reshetikhin-Turaev型），在闭3-流形上（精确）计算其不变量的问题要么可以在多项式时间内求解，要么从该TQFT的融合范畴构建的某些张量的（精确）收缩是#𝖯-困难的。我们的证明应用了Cai和Chen [J. ACM, 2017]关于复加权约束满足问题的二分结果。我们将重新解释Cai和Chen区分两种情况（即#𝖯-困难的张量收缩与多项式时间不变量）的条件，将其转化为融合范畴的术语，留待未来工作。我们期望通过更多努力，我们的归约可以得到改进，从而直接获得3-流形的TQFT不变量的二分法，而不是针对从TQFT融合范畴构建的更一般的张量。
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 #𝖯-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 f...