This thesis is a survey of certain algorithmic problems in group theory and their computational complexities. In particular, it consists of a detailed review of the decidability and complexity of the word and conjugacy problems in several classes of solvable groups, followed by two original results. The first result states that the Conjugacy Problem in wreath products which satisfy certain elementary conditions is decidable in polynomial time. It is largely based on work by Jane Matthews, published in 1969. The second result, based on ideas of Remeslennikov and Sokolov (1970), and Myasnikov, Roman'kov, Ushakov and Vershik (2008) gives a uniform polynomial time algorithm to decide the Conjugacy Problem in free solvable groups. / Cette thèse est une synthèse de certains problèmes algorithmiques dans la thèoriedes groupes et leur complexité computationnelle. Plus particulièrement, elle présenteune revue détaillée de la décidabilité et de la complexité des problèmes du mot et dela conjugaison dans plusieurs classes de groupes solubles, suivie de deux nouveauxrésultats. Le premier résultat énonce que le problème de la conjugaison dans lesproduits couronne qui satisfont certaines conditions élémentaires est décidable entemps polynomial. Elle part d'une publication de Jane Matthews (1969). Le deuxièmerésultat, basé sur des idées de Remeslennikov et Sokolov (1970) et de Myasnikov, Roman'kov,Ushakov et Vershik (2008), présente un algorithme en temps polynomial uniformepour décider le problème de conjugaison dans les groupes solubles libres.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.66827 |
| Date | January 2009 |
| Creators | Vassileva, Svetla |
| Contributors | Alexei Miasnikov (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (Department of Mathematics and Statistics) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0018 seconds