Tricolorable torus knots are NP-complete

摘要

This work presents a method for associating a class of constraint satisfaction problems to a three-dimensional knot. Given a knot, one can build a knot quandle, which is generally an infinite free algebra. The desired collection of problems is derived from the set of invariant relations over the knot quandle, applying theory that relates finite algebras to constraint satisfaction problems. This allows us to develop notions of tractable and NP-complete quandles and knots. In particular, we show that all tricolorable torus knots and all but at most 2 non-trivial knots with 10 or fewer crossings are NP-complete.