Fleischer, Lukas
On the Complexity of the Cayley Semigroup Membership Problem
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 wellknown 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 logspace 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 (quasipolynomial size circuits of constant depth with unbounded fanin) 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 0simple 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:125:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8864},
URN = {urn:nbn:de:0030drops88649},
doi = {10.4230/LIPIcs.CCC.2018.25},
annote = {Keywords: subsemigroup, multiplication table, generators, completeness, quasipolynomialsize circuits, FOLL}
}
2018
Keywords: 

subsemigroup, multiplication table, generators, completeness, quasipolynomialsize circuits, FOLL 
Seminar: 

33rd Computational Complexity Conference (CCC 2018)

Issue date: 

2018 
Date of publication: 

2018 