The conjugacy problem for braid groups $B_3$ and $B_4$ can be solved in polynomial time, it is noted in the paper by Birman, Ko and Lee(2001).

That was a result in 2001. Are there any new results on other small braid groups? Is the conjugacy problem in $B_5$ solvable in polynomial time?

Also, I'm still curious on exactly how fast the conjugacy problem in $B_3$ can be solved(polynomial time is too broad). The only paper that described such algorithm is behind a paywall.


This 2008 paper (freely available) explains the fastest known solution of the conjugacy problem in $B_3$. I think the polynomial time complexity of that solution can be easily extracted from that paper.


This is a longish comment on the $B_3$ case.

$B_3$ is isomorphic to the fundamental group of the complement of a trefoil knot. A trefoil complement fibres over $S^1$ with fiber a once-punctured surface of genus $1$, so $B_3 \simeq F_2 \rtimes \mathbb Z$. So the conjugacy problem in $B_3$ is reducible to a conjugacy problem in $F_2$, the free group on two generators. I believe the action of $\mathbb Z$ on the fiber comes from the hexagonal tiling of the torus. An automorphism of order $6$ about a point of the hexagon induces the monodromy of the bundle.

Conjugacy in a free group can be solved by hyperbolic group / Dehn algorithm techniques (cyclic reduction of words, etc). So I expect this should be quite fast.

  • $\begingroup$ Yes, this would result a linear algorithm for conjugacy problem in $B_3$. $\endgroup$ – Chao Xu Jul 18 '11 at 1:19
  • 1
    $\begingroup$ @Ryan: The conjugacy problem for $F_2 \rtimes \mathbb Z$ does not reduce to the conjugacy problem in $F_2$. The conjugacy problem in $F_2$ is trivial: two cyclically reduced words are conjugate iff they are cyclic shifts of each other. $\endgroup$ – user6976 Jul 18 '11 at 2:37
  • $\begingroup$ Hi Mark. What do you mean by "does not reduce to..." ? By "reduce to" I don't mean they're the same thing, just that you can use the solution of the latter as a step in solving the former problem. The idea is to conjugate elements of $F_2 \rtimes \mathbb Z$ first by elements of $\mathbb Z$, then by elements of $F_2$. In both cases we know the outcome of the action, so technically this reduces to six applications of the solution to the conjugacy problem in $F_2$, one for every outer automorphism of $F_2$ induced by the monodromy. $\endgroup$ – Ryan Budney Jul 18 '11 at 3:18
  • $\begingroup$ @Ryan: I mean that although the conjugacy problem in free-by-cyclic groups is solvable, it is a very non-trivial statement and the complexity is not known. In general the conjugacy problem in a semidirect product $G\rtimes {\mathbb Z}$ may be undecidable even if it is decidable in $G$. $\endgroup$ – user6976 Jul 18 '11 at 4:36
  • 4
    $\begingroup$ @Ryan: There are groups with solvable conjugacy problem which are index 2 subgroups in groups with unsolvable conjugacy problem (and vice versa). As I understand, the easiest solutions of the conjugacy problem in $B_3$ uses the fact that $B_3$ is a central extension of $PSL_2({\mathbb Z})$. It is not trivial and is explained in the 2008 paper by Birman and others. $\endgroup$ – user6976 Jul 18 '11 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.