License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2018.25
URN: urn:nbn:de:0030-drops-88649
URL: http://drops.dagstuhl.de/opus/volltexte/2018/8864/
Go to the corresponding LIPIcs Volume Portal


Fleischer, Lukas

On the Complexity of the Cayley Semigroup Membership Problem

pdf-format:
LIPIcs-CCC-2018-25.pdf (0.5 MB)


Abstract

We investigate the complexity of deciding, given a multiplication table representing a semigroup S, a subset X of S and an element t of S, whether t can be expressed as a product of elements of X. It is well-known that this problem is {NL}-complete and that the more general Cayley groupoid membership problem, where the multiplication table is not required to be associative, is {P}-complete. For groups, the problem can be solved in deterministic log-space which raised the question of determining the exact complexity of this variant. Barrington, Kadau, Lange and McKenzie showed that for Abelian groups and for certain solvable groups, the problem is contained in the complexity class {FOLL} and they concluded that these variants are not hard for any complexity class containing {Parity}. The more general case of arbitrary groups remained open. In this work, we show that for both groups and for commutative semigroups, the problem is solvable in {qAC}^0 (quasi-polynomial size circuits of constant depth with unbounded fan-in) and conclude that these variants are also not hard for any class containing {Parity}. Moreover, we prove that {NL}-completeness already holds for the classes of 0-simple semigroups and nilpotent semigroups. Together with our results on groups and commutative semigroups, we prove the existence of a natural class of finite semigroups which generates a variety of finite semigroups with {NL}-complete Cayley semigroup membership, while the Cayley semigroup membership problem for the class itself is not {NL}-hard. We also discuss applications of our technique to {FOLL}.

BibTeX - Entry

@InProceedings{fleischer:LIPIcs:2018:8864,
  author =	{Lukas Fleischer},
  title =	{{On the Complexity of the Cayley Semigroup Membership Problem}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{25:1--25:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Rocco A. Servedio},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8864},
  URN =		{urn:nbn:de:0030-drops-88649},
  doi =		{10.4230/LIPIcs.CCC.2018.25},
  annote =	{Keywords: subsemigroup, multiplication table, generators, completeness, quasi-polynomial-size circuits, FOLL}
}

Keywords: subsemigroup, multiplication table, generators, completeness, quasi-polynomial-size circuits, FOLL
Seminar: 33rd Computational Complexity Conference (CCC 2018)
Issue Date: 2018
Date of publication: 01.06.2018


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