



01312nas a2200133   4500008004100000245003600041210003500077300001300112490000700125520096100132100001901093700001101112856005501123       2017                        eng d00a3-manifold diagrams and NP vs P0 a3manifold diagrams and NP vs P  a125-141 0 v173 a<p>The computational complexity class #P captures the di_culty of counting the satisfying assignments to a boolean formula. In this work, we use basic tools from quantum computation to give a proof that the SO(3) Witten-Reshetikhin-Turaev (WRT) invariant of 3-manifolds is #P-hard to calculate. We then apply this result to a question about the combinatorics of Heegaard splittings, motivated by analogous work on link diagrams by M. Freedman. We show that, if #P &sube; FPNP, then there exist infinitely many Heegaard splittings which cannot be made logarithmically thin by local WRT-preserving moves, except perhaps via a superpolynomial number of steps. We also outline two extensions of the above results. First, adapting a result of Kuperberg, we show that any presentation-independent approximation of WRT is also #P-hard. Second, we sketch out how all of our results can be translated to the setting of triangulations and Turaev-Viro invariants.</p>1 aAlagic, Gorjan1 aLo, C.  uhttps://dl.acm.org/doi/abs/10.5555/3179483.3179491