A fast algorithm to the conjugacy problem on generic braids

Details A fast algorithm to the conjugacy problem on generic braids A fast algorithm to the conjugacy problem on generic braids

2006-11-15

arxiv.org/abs/math/0611454v3

Mathematics

Geometric Topology

12 pages, 1 figure. to appear in the Proceedings of the International Workshop on Knot Theory for Scientific Objects: OCAMI St

Scientific paper

Random braids that are formed by multiplying randomly chosen permutation braids are studied by analyzing their behavior under Garside's weighted decomposition and cycling. Using this analysis, we propose a polynomial-time algorithm to the conjugacy problem that is successful for random braids in overwhelming probability. As either the braid index or the number of permutation-braid factors increases, the success probability converges to 1 and so, contrary to the common belief, the distribution of hard instances for the conjugacy problem is getting sparser. We also prove a conjecture by Birman and Gonz\'{a}lez-Meneses that any pseudo-Anosov braid can be made to have a special weighted decomposition after taking power and cycling. Moreover we give polynomial upper bounds for the power and the number of iterated cyclings required.

Affiliated with

Also associated with

No associations

Rating

A fast algorithm to the conjugacy problem on generic braids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A fast algorithm to the conjugacy problem on generic braids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A fast algorithm to the conjugacy problem on generic braids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-55086