We will share some recent results that are instructive for approaching the classification of 3d TQFTs and topological order by computational complexity. We show that the Turaev-Viro-Barrett-Westbury state sum TQFT invariants of 3-manifolds that arise from Tambara-Yamagami fusion categories can actually be computed in polynomial time on a classical computer, provided that there is a bound on the first Betti number. On the other hand, if we don’t insist on a bound on the first Betti number, then the invariants should be NP-hard to compute. This talk is based on joint work with Clément Maria and Eric Samperton.