Resumen de A polynomial time algorithm for the conjugacy problem in Zn o Z

Bren Cavallo, Delaram Kahrobaei

• català

  En aquest article introduım un algorisme que, en temps polinomial, resol el problema de la conjugacio (en les seves dues variants, de decisio i de cerca) per a grupsde la forma lliure abelia per infinit cıclic, amb els inputs donats en forma normal. Fem aixo adaptant els resultats de Bogopolski–Martino–Maslakova–Ventura a [1] ide Bogopolski–Martino–Ventura a [2], als grups en questio i, en certs casos, usem un algorisme de Kannan–Lipton [7] per a resoldre el problema de l’`orbita a Zn en temps polinomial.

• English

  In this paper we introduce a polynomial time algorithm that solves both the conjugacy decision and search problems in free abelian-by-innite cyclic groups where the input is elements in normal form. We do this by adapting the work of Bogopolski, Martino, Maslakova, and Ventura in [1] and Bogopolski, Martino, and Ventura in [2], to free abelian-by-innite cyclic groups, and in certain cases apply a polynomial time algorithm for the orbit problem over Zn by Kannan and Lipton [7].Keywords: Conjugacy problem, semidirect product. MSC (2010): Primary 20F10, Secondary 20E06.