Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe computational complexity of determining knot genus in a fixed 3-manifold
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
For a knot diagram we introduce an operation which does not increase the genus of the diagram and does not change its representing knot type. We also describe a condition for this operation to certainly decrease the genus. The proof involves the study of a relation between the genus of a virtual knot diagram and the genus of a knotoid diagram, the former of which has been introduced by Stoimenow, Tchernov and Vdovina, and the latter by Turaev recently. Our operation has a simple interpretation in terms of Gauss codes and hence can easily be computer-implemented.
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.
In an earlier work, we introduced a family of t-modified knot Floer homologies, defined by modifying the construction of knot Floer homology HFK-minus. The resulting groups were then used to define concordance homomorphisms indexed by t in [0,2]. In the present work we elaborate on the special case t=1, and call the corresponding modified knot Floer homology the unoriented knot Floer homology. Using elementary methods (based on grid diagrams and normal forms for surface cobordisms), we show that the resulting concordance homomorphism gives a lower bound for the smooth 4-dimensional crosscap number of a knot K --- the minimal first Betti number of a smooth (possibly non-orientable) surface in the 4-disk that meets the boundary 3-sphere along the given knot K.
This survey focuses on the computational complexity of some of the fundamental decision problems in 3-manifold theory. The article discusses the wide variety of tools that are used to tackle these problems, including normal and almost surfaces, hierarchies, homomorphisms to finite groups, and hyperbolic structures.
We prove foundational results about the set of homomorphisms from a finitely generated group to the collection of all fundamental groups of compact 3-manifolds and answer questions of Reid-Wang-Zhou and Agol-Liu.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
