The subjects of this thesis are the algorithmic solution to the conjugacy problem on generic braids and the solution to the reducibility problem.
In chapter 1, we introduce the conjugacy problem on braid groups and three dynamic types of braids.
In chapter 2, We study random braids that are formed by multiplying randomly chosen permutation braids by analyzing their behavior under 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 show that some power of a pseudo-Anosov braid is always cyclically weighted up to cycling and we also give upper bounds for the necessary exponent and the necessary number of iterated cyclings.
In chapter 3, We propose an algorithm for deciding the dynamic type of a given braid. The algorithm is based on Garside's weighted decomposition and is polynomial-time in the word-length of an input braid. Moreover a reduction system of circles can be found if the input is a certain type of reducible braids.
본 논문은 일반적 땋임의 공액 문제에 대한 해와 땋임의 동역학 종류에 대한 판별 문제의 해에 관해서 연구한다.
1장에서는 땋임 군을 중요한 개념들을 소개한다. 그리고 공액 문제와 그것의 해를 주는 중요한 공액 불변 집합들을 소개하고 그것들의 중요한 성질에 대해서 알아본다. 그리고 닐슨-서스턴 곡면사상으로서의 땋임의 동역학 종류를 소개한다.
2장에서는 무작위로 선택된 순열 땋임의 곱으로 만들어진 일반적 땋임의 가중 분해와 순환 연산에 대해 분석한다. 그리고 이 분석을 이용하여 압도적인 확률로 일반적 땋임의 공액 문제의 올바른 해를 주는 다항시간 알고리즘을 소개한다. 이 알고리즘은 땋임 지수와 순열 땋임의 수가 증가할수록 공액 문제의 올바른 해를 구할 확률이 땋임 지수와 순열 땋임의 수가 증가할수록 1에 가까워짐을 보인다. 또한, 유사-아노소프 땋임은 땋임의 적당한 제곱과 반복적인 순환 연산을 통하여 항상 순환 가중형태가 됨을 보인다. 그리고 그것들의 상한을 제시한다.
3장에서는 땋임의 동역학 종류에 대한 판별 문제의 해를 주는 다항시간 알고리즘을 제안한다. 가사이드의 가중 분해에 기반을 둔 이 알고리즘은 땋임의 단어 길이에 대하여 다항 시간임을 보인다.
