Journaly anna hass code#
Normal surfaces are parameterized by vectors v in Z 7t, which code the way the surface intersects each tetrahedron.
Journaly anna hass plus#
įor a given link diagram with crossing measure n (the number of vertices plus the number of components minus 1), the authors construct a triangulated link complement having t?420n tetrahedra. To show that the link is a trivial knot, one needs to find a disk in M K (an “essential disk”) whose boundary has nontrivial Z 2 homology in the homology of the boundary of M K. The tetrahedra of the triangulation not belonging to the tubular neighborhoods form the “link complement” M K. An appropriate triangulation includes a tubular neighborhood of each knot, and the link itself lies on its 1-skeleton. It is convenient to work in the 3-sphere, which can be triangulated in a way that is adapted to the link. These algorithms are based on the use of normal surfaces and decision procedures due to Haken and others, which are applied to the piecewise-linear category. Exponential worst-case running time bounds for deterministic algorithms to solve each of these problems are given. The splitting problem (determining if a link is splittable) is also shown to be in NP. A link is “splittable” if it is isotopic to the union of two links that can be separated by a plane. The first question is to determine whether a given link diagram represents a trivial knot. The projection is chosen to be in “general position” so that all vertices of the link diagram have degree 4. An edge of the link diagram corresponds to the portion of a link between two crossings. Its vertices are the crossings of the projection and are specially labeled to indicate which edge of the projection passes over the other. This is a planar graph obtained by projection of the link. A knot is “trivial” if it is isotopic to a (simple) plane polygon.Ī link is represented by a link diagram. A finite collection of disjoint knots is a “link.” Two knots are “isotopic” if there is a (piecewise-linear) isotopy transforming one to the other. Google Scholarįor the purposes of this paper, a “knot” is a simple polygon in 3-space. In Graph Structure Theory (Seattle, Wash. Knots and braids: Some algorithmic questions. North-Holland, Amsterdam, The Netherlands, pp. Cambridge University Press, Cambridge, Mass. Complexity: Knots, Colourings and Counting. In Proceedings of the Symposium on Pure Mathematics, vol. Recent results on sufficiently large 3-manifolds. Ueber die topologischen Invarianten mehrdimensionaler Mannigfaltigkeiten. Classical Topology and Combinatorial Group Theory. Waterloo Press, Waterloo, Ont., Canada, pp. In Integer Programming and Combinatorial Optimization, R. Hilbert bases, Caratheodory's theorem and combinatorial optimization. Bestimmung der Primfactor zerlegung von Verkettungen. Theory of linear and integer programming. Relationship between nondeterministic and deterministic tape classes. Publish or Perish, Inc., Berkeley, Calif. (English translation: BORON, L., CHRISTENSON, C., AND SMITH, B., BCS Associates, Moscow, Ind., 1983.) Google Scholar Grenzgeb., Bd., 1, Springer-Verlag, Berlin. Recursive unsolvability of group-theoretic problems.
On Dehn's lemma and the asphericity of knots. Affine structures in 3-manifolds V: The triangulation theorem and Hauptvermutung. Classifications of sufficiently large 3-manifolds. Geschlossene Flachen in dreidimensionalen Mannigfaltigkeiten. A polynomial invariant of knots via von Neumann algebras. On the Computational Complexity of the Jones and Tutte Polynomials. Algorithms for the complete decomposition of a closed 3-manifold. PL Equivariant Surgery and Invariant Decompositions of 3-Manifolds. An algorithm to decide if a 3-manifold is a Haken manifold. In Combinatorial Group Theory and Topology, Annals of Mathematical Studies, No. Princeton University Press, Princeton, N.J. Oxford University Press, Oxford, England. The Classification of Knots and 3-Dimensional Spaces. On the classification of homeomorphisms of 2-manifolds and the classification of 3-manifolds. IEEE Computer Science Press, Los Alamitos, Calif., pp. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (Miami, Fla., Oct.). The computational complexity of knot and link problems, preliminary report. The number of Reidemeister moves needed for unknotting. Algorithms for recognizing knots and 3-manifolds, Chaos, Solitons Fractals. Theorie der Normalflachen, ein Isotopiekriterium ffir den Kreisknoten. A guide to the theory of NP-completeness. Uber die Topologie des dreidimensional Raumes.
Topological invariants of knots and links. An elementary introduction to the mathematical theory of knots.
0 kommentar(er)
