Balanced and almost balanced group presentations from algorithmic viewpoint
| Thesis title in Czech: | Balancované a téměř balancované prezentace grup z algoritmického pohledu |
|---|---|
| Thesis title in English: | Balanced and almost balanced group presentations from algorithmic viewpoint |
| Key words: | Prezentace grup, algoritmus, problém triviality, Andrews-Curtisova domněnka |
| English key words: | Group presentation, algorithm, triviality problem, Andrews-Curtis conjecture |
| Academic year of topic announcement: | 2017/2018 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. RNDr. Martin Tancer, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 12.10.2017 |
| Date of assignment: | 16.10.2017 |
| Confirmed by Study dept. on: | 23.10.2017 |
| Date and time of defence: | 18.09.2018 09:00 |
| Date of electronic submission: | 19.07.2018 |
| Date of submission of printed version: | 20.07.2018 |
| Date of proceeded defence: | 18.09.2018 |
| Opponents: | RNDr. Pavel Paták, Ph.D. |
| Guidelines |
| V této práci se její řešitel zaměří na studium prezentací grup z algoritmického úhlu pohledu. Především půjde o balancované prezentace (stejný počet symbolů a relací) nebo skoro balancované prezentace (počet relací omezený nějakou funkcí počtu symbolů). Konkrétní dílčí úkoly jsou:
- Nastudovat literaturu a sepsat pojednání o tématu. - Zaměřit se na "výpočetní sílu" problému triviality grupy zadané pomocí balancované či skoro balancované prezentace. Zejména s ohledem na to, jaké výpočetní problémy lze pomocí problému triviality simulovat. Dálší možné rozšiřující úkoly například jsou: - Zaměřit se na souvislost s Andrews-Curtisovou domněnkou, např. na studium konkrétních známych potenciálních protipříkladů. - Zaměřit se na topologické aspekty balancovaných či skoro balancovaných prezentací, tj. popsat topologické souvislosti a studovat, jaké topologické vlastnosti mohou mít vliv na výpočetní sílu. - Naprogramovat heuristické nástroje pro potvrzení triviality/netriviality. |
| References |
| M. R. Bridson. The complexity of balanced presentations and the Andrews-Curtis conjecture, preprint 2015. https://arxiv.org/abs/1504.04187
Miasnikov, Alexei D., and Alexei G. Myasnikov. Balanced presentations of the trivial group on two generators and the Andrews-Curtis conjecture. Groups and Computation III (W. Kantor and A. Seress, eds.), de Gruyter, Berlin (2001): 257-263. Další literatura bude doplněna dle postupu práce. |