Low complexity algorithms in knot theory

2018/03/13 by Kharlampovich, Olga, Vdovina, Alina
#20F10 #57M27 #Combinatorics (math.CO) #FOS: Mathematics #Geometric Topology (math.GT) #Group Theory (math.GR)

paper · doi:10.48550/arxiv.1803.04908

Abstract

We show that the genus problem for alternating knots with n crossings has linear time complexity and is in Logspace(n). Almost all alternating knots of given genus possess additional combinatorial structure, we call them standard. We show that the genus problem for these knots belongs to TC⁰ circuit complexity class. We also show, that the equivalence problem for such knots with n crossings has time complexity nlog (n) and is in Logspace(n) and TC⁰ complexity classes.

Related

• Braid ordering and knot genus
• Polynomial algorithm for alternating link equivalence
• On the complexity of meander-like diagrams of knots
• A lower bound on the average genus of a 2-bridge knot
• An Algorithmic Approach to Classify Knots