Mathematics & Informatics An Efficient Algorithm to Decide the Knot Problem

ABSTRACT. We study knot representations by sequences α of oriented arcs x1, x2,..., xm, which are connected, alternating below and above the 2-sphere S2 with a crossing free projection on a segment of a circle on the S2, the starting point A of x1 is connected with the end point B of xm by a crossing free string L on S2 oriented from B to A. Each knot projection we represent by such a pair (α,L). Each such representation can be described uniquely up to isomorphisms of the 2-sphere by its signature, a finite word σ(α,L) over an alphabet. X:{x1 ε1, x2 ε2,...,xm εm}, εi∈{1,–1}. We define transformations of the knot projections K on S2 called normalizations or extended normalizations into arcade-string representations (αK,LK) called AFL. These constructions define to each knot Κ a formal language LΚ defined by the set of the signatures σαK of the normalizations of the projections K of the knot Κ. The equivalence of knots Κ and Κ ′ can be described by the relation ∅≠ΚΚ LL I. We prove that this relation is decidable in time) ( 32 2 nnO ⋅ for projections K, K ′ with n ≥ the numbers of the crossing points of K and K′. If K ′ is a circle the equivalence is decidable in time) ( 32 nO. © 2008 Bull. Georg. Natl. Acad. Sci. Key words: knot problem, AFL representation of knots, Reidemeister moves