Computational complexity and 3-manifolds and zombies

DOI10.2140/GT.2018.22.3623MaRDI QIDQ6288926arXivWikidataFDO

Publication date 12 July 2017

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Finite-type and quantum invariants, topological quantum field theories (TQFT) (57K16) Invariants of 3-manifolds (including skein modules, character varieties) (57K31)

Abstract: We show the problem of counting homomorphisms from the fundamental group of a homology

3

-sphere

M

to a finite, non-abelian simple group

G

is #P-complete, in the case that

G

is fixed and

M

is the computational input. Similarly, deciding if there is a non-trivial homomorphism is NP-complete. In both reductions, we can guarantee that every non-trivial homomorphism is a surjection. As a corollary, for any fixed integer

m g e 5

, it is NP-complete to decide whether

M

admits a connected

m

-sheeted covering. Our construction is inspired by universality results in topological quantum computation. Given a classical reversible circuit

C

, we construct

M

so that evaluations of

C

with certain initialization and finalization conditions correspond to homomorphisms

p i_{1} (M) o G

. An intermediate state of

C

likewise corresponds to a homomorphism

p i_{1} (S i g m a_{g}) o G

, where

S i g m a_{g}

is a pointed Heegaard surface of

M

of genus

g

. We analyze the action on these homomorphisms by the pointed mapping class group

e x t {M C G}_{*} (S i g m a_{g})

and its Torelli subgroup

e x t {T o r}_{*} (S i g m a_{g})

. By results of Dunfield-Thurston, the action of

e x t {M C G}_{*} (S i g m a_{g})

is as large as possible when

g

is sufficiently large; we can pass to the Torelli group using the congruence subgroup property of

e x t S p (2 g, m a t h b b Z)

. Our results can be interpreted as a sharp classical universality property of an associated combinatorial

(2 + 1)

-dimensional TQFT.

This page was built for publication: Computational complexity and 3-manifolds and zombies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6288926)