Knots and Links - Introduction and Complexity ResultsOutlineDefinitionsSlide 4Classification of KnotsComputational RepresentationUnknotting ProblemSlide 8Splitting ProblemGenus of a surfaceSlide 11Genus of a knotSlide 133-Manifold Knot GenusSlide 15A Special CaseRecapOpen ProblemsReferencesKnots and Links - Introduction and Complexity ResultsKrishnaram Kenthapadi11/27/2002OutlineDefinitionClassificationRepresentationKnot TrivialitySplitting ProblemGenus ProblemOpen QuestionsDefinitionsKnot – A closed curve embedded in space as a simple (non-self-intersecting) polygon with finitely many edges. (Informally, a thin elastic string with extremities glued together)DefinitionsLink – A finite collection of simple polygons disjointly embedded in 3-dimensional space.Individual polygons -components of linkKnot – A link with one componentClassification of KnotsIsotopy is a deformation of knots s.t.Piecewise linear & continuousPolygon remains simple throughoutDefines an equivalence relationKnots in a single plane are equivalent Trivial knotsComputational RepresentationPolygonal Representation in 3-D spaceList the vertices of each polygon in orderLink diagram representing a 2-D projectionExtra labeling for crossesBoth are polynomial time equivalentUnknotting ProblemInstance : A link diagram DQuestion : Is D a knot diagram that represents the trivial knot? This problem is in NP. (Hass, Lagarias & Pippenger, 1999)Unknotting ProblemHaken’s Algorithm (1961): Runs in exponential time. Reidemeister moves : Combinatorial transformations on the knot diagram that don’t change the equivalence class of the knot.A knot diagram is unknotted if there exists a finite sequence of Reidemeister moves that converts it to the trivial knot diagram.But how many steps?Splitting ProblemInstance : A link diagram DQuestion : Is the link represented by D splittable?Splittable : the polygons can be separated by piecewise linear isotopy. This problem is in NP.Genus of a surfaceAny oriented surface without boundary can be obtained from a sphere by adding “handles”.Genus = Number of handlesEg: Genus of Sphere is 0, Torus is 1, etc.Genus of a surfaceGenus is also the number of surfaces along which a surface can be cut while leaving it connected.Surface with boundary : Glue a disk to each component of the boundary (“capping off”) and then obtain the genus.Genus of a knotInformally, the degree of “knottedness” of a curve.S(K) – class of all orientable spanning surfaces for a knot K, ie, surfaces embedded in the manifold, with a single boundary component that coincides with K.S(K) is non-empty for any knot in 3-sphere (Seifert, 1935). Seifert also showed a construction.Genus of a knotGenus(K) = min{Genus(s) | s \in S(K)} if S(K) is non-empty; otherwise Genus(K) is infinity ().3-Manifold Knot GenusInstance: A triangulated 3-manifold M, a knot K and a natural number,g.Question: Is genus(K) <= g ?Size of instance : Number of tetrahedra in M and log(g).This problem is NP-complete. (Agol, Hass & Thurston, 2002)3-Manifold Knot GenusNP- hard: By reduction from an NP-complete problem, ONE-IN-THREE-SAT. ONE-IN-THREE-SAT:Instance: A set U of variables and a collection C of clauses (of three literals each) over U.Question: Is there a truth assignment for U s.t. each clause in C has exactly one true literal?A Special CaseA knot is trivial if its genus is zero.Hence, Unknotting problem is a special case of 3-Manifold Knot Genus (with the input, g = 0).RecapDefinition of knots & links. Classification – knot isotopyComputational Representationpolygonal (3D) link diagram (2D)Knot Triviality is in NPSplitting Problem is in NPGenus Problem is NP-completeOpen ProblemsIs 3-SPHERE KNOT GENUS NP-hard?Is determining genus of a knot in 3-Manifold in NP?Amounts to showing a lower boundIf “yes”, UNKNOTTING problem is in both NP and co-NPReferences1. C. C. Adams, The Knot Book. An elementary introduction to the mathematical theory of knots, W. H. Freeman, New York 1994.2. V.V.Prasolov, Intuitive Topology, American Mathematical Society, 1995.3. J. Hass, J. C. Lagarias and N. Pippenger, The computational complexity of Knot and Link problems", Journal of the ACM, 46 (1999) 185-211.4. I. Agol, J. Hass and W.P. Thurston, The Computational Complexity of Knot Genus and Spanning Area, Proceedings of STOC
View Full Document