Seminar

Many classical problems from knot theory and low-dimensional topology can be formulated as decision problems. Quite a few of them are now known to lie in complexity classes NP or co-NP, which is an upper bound on computational complexity. At the same time, only several such problems are known to be NP-hard, which is a lower bound. Even fewer such non-trivial problems are known to have a polynomial algorithm. We will discuss some such results related to 3-manifold triangulations and homeomorphism, unknotting number, and link equivalence. The proofs use tools from low-dimensional topology and knot theory, at times mixing them with algorithmic complexity theory and topological graph theory.