DOC PREVIEW
Stanford CS 468 - Knots and Links - Introduction and Complexity Results

This preview shows page 1-2-3-4-5-6 out of 19 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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/2002OutlineDefinitionClassificationRepresentationKnot TrivialitySplitting ProblemGenus ProblemOpen QuestionsDefinitionsKnot – 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)DefinitionsLink – A finite collection of simple polygons disjointly embedded in 3-dimensional space.Individual polygons -components of linkKnot – A link with one componentClassification of KnotsIsotopy is a deformation of knots s.t.Piecewise linear & continuousPolygon remains simple throughoutDefines an equivalence relationKnots in a single plane are equivalent Trivial knotsComputational RepresentationPolygonal Representation in 3-D spaceList the vertices of each polygon in orderLink diagram representing a 2-D projectionExtra labeling for crossesBoth are polynomial time equivalentUnknotting ProblemInstance : A link diagram DQuestion : Is D a knot diagram that represents the trivial knot? This problem is in NP. (Hass, Lagarias & Pippenger, 1999)Unknotting ProblemHaken’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 ProblemInstance : A link diagram DQuestion : 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 surfaceAny oriented surface without boundary can be obtained from a sphere by adding “handles”.Genus = Number of handlesEg: Genus of Sphere is 0, Torus is 1, etc.Genus of a surfaceGenus 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 knotInformally, 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 knotGenus(K) = min{Genus(s) | s \in S(K)} if S(K) is non-empty; otherwise Genus(K) is infinity ().3-Manifold Knot GenusInstance: 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 GenusNP- 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 CaseA 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).RecapDefinition of knots & links. Classification – knot isotopyComputational Representationpolygonal (3D) link diagram (2D)Knot Triviality is in NPSplitting Problem is in NPGenus Problem is NP-completeOpen ProblemsIs 3-SPHERE KNOT GENUS NP-hard?Is determining genus of a knot in 3-Manifold in NP?Amounts to showing a lower boundIf “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

Stanford CS 468 - Knots and Links - Introduction and Complexity Results

Download Knots and Links - Introduction and Complexity Results
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Knots and Links - Introduction and Complexity Results and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Knots and Links - Introduction and Complexity Results 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?