Complexity of some algorithmic problems in groups: a survey
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916094946574336 |
|---|---|
| author | Shpilrain, Vladimir |
| author_facet | Shpilrain, Vladimir |
| contents | In this survey, we address the worst-case, average-case, and generic-case time complexity of the word problem and some other algorithmic problems in several classes of groups and show that it is often the case that the average-case complexity of the word problem is linear with respect to the length of an input word, which is as good as it gets if one considers groups given by generators and defining relations. At the same time, there are other natural algorithmic problems, for instance, the geodesic (decision) problem or Whitehead's automorphism problem, where the average-case time complexity can be sublinear, even constant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_09218 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity of some algorithmic problems in groups: a survey Shpilrain, Vladimir Group Theory Computational Complexity In this survey, we address the worst-case, average-case, and generic-case time complexity of the word problem and some other algorithmic problems in several classes of groups and show that it is often the case that the average-case complexity of the word problem is linear with respect to the length of an input word, which is as good as it gets if one considers groups given by generators and defining relations. At the same time, there are other natural algorithmic problems, for instance, the geodesic (decision) problem or Whitehead's automorphism problem, where the average-case time complexity can be sublinear, even constant. |
| title | Complexity of some algorithmic problems in groups: a survey |
| topic | Group Theory Computational Complexity |
| url | https://arxiv.org/abs/2401.09218 |