Reduction of the group isomorphism problem to the group automorphism problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916639564365824 |
|---|---|
| author | Skresanov, Saveliy V. |
| author_facet | Skresanov, Saveliy V. |
| contents | It is well known that the graph isomorphism problem is polynomial-time reducible to the graph automorphism problem (in fact these two problems are polynomial-time equivalent). We show that, analogously, the group isomorphism problem is polynomial-time reducible to the group automorphism problem. Reductions to other relevant problems like automorphism counting are also given. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_01180 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reduction of the group isomorphism problem to the group automorphism problem Skresanov, Saveliy V. Computational Complexity Group Theory 68Q25 (Primary) 20D45 (Secondary) It is well known that the graph isomorphism problem is polynomial-time reducible to the graph automorphism problem (in fact these two problems are polynomial-time equivalent). We show that, analogously, the group isomorphism problem is polynomial-time reducible to the group automorphism problem. Reductions to other relevant problems like automorphism counting are also given. |
| title | Reduction of the group isomorphism problem to the group automorphism problem |
| topic | Computational Complexity Group Theory 68Q25 (Primary) 20D45 (Secondary) |
| url | https://arxiv.org/abs/2503.01180 |