{"id":"arxiv/2601.02119","url":"https://arxiv.org/abs/2601.02119","tags":["math.GT","math.CO"],"score":0,"title":"On computational complexity of Khovanov homology","domain":"math.GT","source":"arxiv","authors":["Tuomas Kelomäki","Dirk Schütz"],"reviews":0,"subject":"math.GT","summary":"Computing the Jones polynomial of general link diagrams is known to be $\\#$P-hard, while restricting the computation to braid closures on fixed number of strands allows for a polynomial time algorithm. We investigate polynomial time algorithms for Khovanov homology of braids and show that for $3$-braids there is one. In contrast, we show that Bar-Natan's scanning algorithm runs in exponential time when restricted to simple classes of $3$-braids. For more general braids, we obtain that a variation of the scanning algorithm computes the Khovanov homology for a bounded set of homological…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-05","reactions":{}}