On computational complexity of Khovanov homology
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917184769359872 |
|---|---|
| author | Kelomäki, Tuomas Schütz, Dirk |
| author_facet | Kelomäki, Tuomas Schütz, Dirk |
| contents | 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 degrees in polynomial time. We also prove upper and lower bounds on the ranks of Khovanov homology groups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_02119 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On computational complexity of Khovanov homology Kelomäki, Tuomas Schütz, Dirk Geometric Topology Combinatorics 57K18 (Primary) 57K10 (Secondary) 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 degrees in polynomial time. We also prove upper and lower bounds on the ranks of Khovanov homology groups. |
| title | On computational complexity of Khovanov homology |
| topic | Geometric Topology Combinatorics 57K18 (Primary) 57K10 (Secondary) |
| url | https://arxiv.org/abs/2601.02119 |