Geodesic
ON THE CONJUGACY PROBLEM IN CERTAIN METABELIAN GROUPS
Glasgow mathematical journal, Tome 61 (2019) no. 2, pp. 251-269

Voir la notice de l'article provenant de la source Cambridge University Press

We analyze the computational complexity of an algorithm to solve the conjugacy search problem in a certain family of metabelian groups. We prove that in general the time complexity of the conjugacy search problem for these groups is at most exponential. For a subfamily of groups, we prove that the conjugacy search problem is polynomial. We also show that for a different subfamily the conjugacy search problem reduces to the discrete logarithm problem. 
GRYAK, JONATHAN; KAHROBAEI, DELARAM; MARTINEZ-PEREZ, CONCHITA. ON THE CONJUGACY PROBLEM IN CERTAIN METABELIAN GROUPS. Glasgow mathematical journal, Tome 61 (2019) no. 2, pp. 251-269. doi: 10.1017/S0017089518000198
@article{10_1017_S0017089518000198,
     author = {GRYAK, JONATHAN and KAHROBAEI, DELARAM and MARTINEZ-PEREZ, CONCHITA},
     title = {ON {THE} {CONJUGACY} {PROBLEM} {IN} {CERTAIN} {METABELIAN} {GROUPS}},
     journal = {Glasgow mathematical journal},
     pages = {251--269},
     year = {2019},
     volume = {61},
     number = {2},
     doi = {10.1017/S0017089518000198},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/S0017089518000198/}
}
TY  - JOUR
AU  - GRYAK, JONATHAN
AU  - KAHROBAEI, DELARAM
AU  - MARTINEZ-PEREZ, CONCHITA
TI  - ON THE CONJUGACY PROBLEM IN CERTAIN METABELIAN GROUPS
JO  - Glasgow mathematical journal
PY  - 2019
SP  - 251
EP  - 269
VL  - 61
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.1017/S0017089518000198/
DO  - 10.1017/S0017089518000198
ID  - 10_1017_S0017089518000198
ER  - 
%0 Journal Article
%A GRYAK, JONATHAN
%A KAHROBAEI, DELARAM
%A MARTINEZ-PEREZ, CONCHITA
%T ON THE CONJUGACY PROBLEM IN CERTAIN METABELIAN GROUPS
%J Glasgow mathematical journal
%D 2019
%P 251-269
%V 61
%N 2
%U http://geodesic.mathdoc.fr/articles/10.1017/S0017089518000198/
%R 10.1017/S0017089518000198
%F 10_1017_S0017089518000198

[1] 1. Auslander, L., On a problem of {P}hilip {H}all, Ann. Math. 86 (1) (1967), 112–116. Google Scholar

[2] 2. Babai, L., Beals, R., Cai, J.-Y., Ivanyos, G. and Luks, E. M., Multiplicative equations over commuting matrices, in Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms (SODA), 1996. Google Scholar

[3] 3. Baumslag, G. and Bieri, R., Constructable solvable groups, Math. Z. 151 (3) (1976), 249–257. Google Scholar

[4] 4. Cavallo, B. and Kahrobaei, D., A polynomial time algorithm for the conjugacy problem in , Reports@SCM 1 (1), 2014. Google Scholar

[5] 5. Eick, B. and Ostheimer, G., On the orbit-stabilizer problem for integral matrix actions of polycyclic groups, Math. Comput. 72 (243) (2003), 1511–1529. Google Scholar

[6] 6. Holt, D. F., Eick, B. and O'Brien, E. A., Handbook of computational group theory (Chapman & Hall/CRC, Boca Raton, 2005). Google Scholar

[7] 7. Horn, R. A. and Johnson, C. R., Matrix analysis (Cambridge University Press, New York, 1985). Google Scholar

[8] 8. Kannan, R. and Bachem, A., Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8 (4) (1979), 499–507. Google Scholar

[9] 9. Lennox, J. C. and Robinson, D. J. S., The theory of infinite soluble groups. Oxford mathematical monographs (The Clarendon Press, Oxford University Press, Oxford, 2004). Google Scholar

[10] 10. Noskov, G. A., Conjugacy problem in metabelian groups, Math. Notes Acad. Sci. USSR 31 (4) (1982), 252–258. Google Scholar

[11] 11. Sims, C. C., Computation with finitely presented groups, vol. 48 (Cambridge University Press, New York, 1994). Google Scholar

[12] 12. Yap, C. K., Linear systems, in Fundamental Problems of Algorithmic Algebra, Chapter 10, (Oxford University Press, New York, 2000), 258–299. Google Scholar

Cité par Sources :