Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputational complexity and 3-manifolds and zombies
114
0
0.0
(
0
)
Added by
Greg Kuperberg
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Authors
Greg Kuperberg
Ask ChatGPT about the research
No Arabic 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 ge 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 $pi_1(M) to G$. An intermediate state of $C$ likewise corresponds to a homomorphism $pi_1(Sigma_g) to G$, where $Sigma_g$ is a pointed Heegaard surface of $M$ of genus $g$. We analyze the action on these homomorphisms by the pointed mapping class group $text{MCG}_*(Sigma_g)$ and its Torelli subgroup $text{Tor}_*(Sigma_g)$. By results of Dunfield-Thurston, the action of $text{MCG}_*(Sigma_g)$ is as large as possible when $g$ is sufficiently large; we can pass to the Torelli group using the congruence subgroup property of $text{Sp}(2g,mathbb{Z})$. Our results can be interpreted as a sharp classical universality property of an associated combinatorial $(2+1)$-dimensional TQFT.
rate research
Read More
The triangulation complexity of a closed orientable 3-manifold is the minimal number of tetrahedra in any triangulation of the manifold. The main theorem of the paper gives upper and lower bounds on the triangulation complexity of any closed orientable hyperbolic 3-manifold that fibres over the circle. We show that the triangulation complexity of the manifold is equal to the translation length of the monodromy action on the mapping class group of the fibre, up to a bounded factor, where the bound depends only on the genus of the fibre.
We prove that any mapping torus of a closed 3-manifold has zero simplicial volume. When the fiber is a prime 3-manifold, classification results can be applied to show vanishing of the simplicial volume, however the case of reducible fibers is by far more subtle. We thus analyse the possible self-homeomorphisms of reducible 3-manifolds, and use this analysis to produce an explicit representative of the fundamental class of the corresponding mapping tori. To this end, we introduce a new technique for understanding self-homeomorphisms of connected sums in arbitrary dimensions on the level of classifying spaces and for computing the simplicial volume. In particular, we extend our computations to mapping tori of certain connected sums in higher dimensions. Our main result completes the picture for the vanishing of the simplicial volume of fiber bundles in dimension four. Moreover, we deduce that dimension four together with the trivial case of dimension two are the only dimensions where all mapping tori have vanishing simplicial volume. As a group theoretic consequence, we derive an alternative proof of the fact that the fundamental group $G$ of a mapping torus of a 3-manifold $M$ is Gromov hyperbolic if and only if $M$ is virtually a connected sum $# S^2times S^1$ and $G$ does not contain $mathbb{Z}^2$.
The Turaev-Viro invariants are a powerful family of topological invariants for distinguishing between different 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them require exponential time. The invariants are parameterised by an integer $r geq 3$. We resolve the question of complexity for $r=3$ and $r=4$, giving simple proofs that computing Turaev-Viro invariants for $r=3$ is polynomial time, but for $r=4$ is #P-hard. Moreover, we give an explicit fixed-parameter tractable algorithm for arbitrary $r$, and show through concrete implementation and experimentation that this algorithm is practical---and indeed preferable---to the prior state of the art for real computation.
Let $G$ be a nonabelian, simple group with a nontrivial conjugacy class $C subseteq G$. Let $K$ be a diagram of an oriented knot in $S^3$, thought of as computational input. We show that for each such $G$ and $C$, the problem of counting homomorphisms $pi_1(S^3setminus K) to G$ that send meridians of $K$ to $C$ is almost parsimoniously $mathsf{#P}$-complete. This work is a sequel to a previous result by the authors that counting homomorphisms from fundamental groups of integer homology 3-spheres to $G$ is almost parsimoniously $mathsf{#P}$-complete. Where we previously used mapping class groups actions on closed, unmarked surfaces, we now use braid group actions.
We show that the problem of determining the genus of a knot in a fixed compact, orientable three-dimensional manifold lies in NP. This answers a question asked by Agol, Hass, and Thurston in 2002. Previously, this was known for rational homology three-spheres, by the work of the first author.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
