Affordable Access

deepdyve-link
Publisher Website

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

Authors
Type
Preprint
Publication Date
Submission Date
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.

Statistics

Seen <100 times