License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.126
URN: urn:nbn:de:0030-drops-125339
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12533/
Figelius, Michael ;
Ganardi, Moses ;
Lohrey, Markus ;
Zetzsche, Georg
The Complexity of Knapsack Problems in Wreath Products
Abstract
We prove new complexity results for computational problems in certain wreath products of groups and (as an application) for free solvable groups. For a finitely generated group we study the so-called power word problem (does a given expression u₁^{k₁} … u_d^{k_d}, where u₁, …, u_d are words over the group generators and k₁, …, k_d are binary encoded integers, evaluate to the group identity?) and knapsack problem (does a given equation u₁^{x₁} … u_d^{x_d} = v, where u₁, …, u_d,v are words over the group generators and x₁,…,x_d are variables, have a solution in the natural numbers). We prove that the power word problem for wreath products of the form G ≀ ℤ with G nilpotent and iterated wreath products of free abelian groups belongs to TC⁰. As an application of the latter, the power word problem for free solvable groups is in TC⁰. On the other hand we show that for wreath products G ≀ ℤ, where G is a so called uniformly strongly efficiently non-solvable group (which form a large subclass of non-solvable groups), the power word problem is coNP-hard. For the knapsack problem we show NP-completeness for iterated wreath products of free abelian groups and hence free solvable groups. Moreover, the knapsack problem for every wreath product G ≀ ℤ, where G is uniformly efficiently non-solvable, is Σ₂^p-hard.
BibTeX - Entry
@InProceedings{figelius_et_al:LIPIcs:2020:12533,
author = {Michael Figelius and Moses Ganardi and Markus Lohrey and Georg Zetzsche},
title = {{The Complexity of Knapsack Problems in Wreath Products}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {126:1--126:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12533},
URN = {urn:nbn:de:0030-drops-125339},
doi = {10.4230/LIPIcs.ICALP.2020.126},
annote = {Keywords: algorithmic group theory, knapsack, wreath product}
}
|
Keywords: |
|
algorithmic group theory, knapsack, wreath product |
|
Collection: |
|
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
29.06.2020 |
