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.102
URN: urn:nbn:de:0030-drops-125093
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12509/
Go to the corresponding LIPIcs Volume Portal

Weiß, Armin

Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis

pdf-format:
LIPIcs-ICALP-2020-102.pdf (0.6 MB)

Abstract

Goldmann and Russell (2002) initiated the study of the complexity of the equation satisfiability problem in finite groups by showing that it is in ? for nilpotent groups while it is ??-complete for non-solvable groups. Since then, several results have appeared showing that the problem can be solved in polynomial time in certain solvable groups of Fitting length two. In this work, we present the first lower bounds for the equation satisfiability problem in finite solvable groups: under the assumption of the exponential time hypothesis, we show that it cannot be in ? for any group of Fitting length at least four and for certain groups of Fitting length three. Moreover, the same hardness result applies to the equation identity problem.

BibTeX - Entry

@InProceedings{wei:LIPIcs:2020:12509,
  author =	{Armin Wei{\ss}},
  title =	{{Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{102:1--102:19},
  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/12509},
  URN =		{urn:nbn:de:0030-drops-125093},
  doi =		{10.4230/LIPIcs.ICALP.2020.102},
  annote =	{Keywords: equations in groups, solvable groups, exponential time hypothesis}
}

Keywords: equations in groups, solvable groups, exponential time hypothesis
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI