Affordable Access

deepdyve-link
Publisher Website

A family of polycyclic groups over which the uniform conjugacy problem is NP-complete

Authors
  • Cavallo, Bren
  • Kahrobaei, Delaram
Type
Preprint
Publication Date
Oct 20, 2014
Submission Date
Mar 17, 2014
Identifiers
DOI: 10.1142/S0218196714500234
Source
arXiv
License
Yellow
External links

Abstract

In this paper we study the conjugacy problem in polycyclic groups. Our main result is that we construct polycyclic groups $G_n$ whose conjugacy problem is at least as hard as the subset sum problem with $n$ indeterminates. As such, the conjugacy problem over the groups $G_n$ is NP-complete where the parameters of the problem are taken in terms of $n$ and the length of the elements given on input.

Report this publication

Statistics

Seen <100 times