License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.4
URN: urn:nbn:de:0030-drops-176560
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17656/
Go to the corresponding LIPIcs Volume Portal

Aichinger, Erhard ; Grünbacher, Simon

The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term

pdf-format:
LIPIcs-STACS-2023-4.pdf (0.8 MB)

Abstract

We consider finite algebraic structures and ask whether every solution of a given system of equations satisfies some other equation. This can be formulated as checking the validity of certain first order formulae called quasi-identities. Checking the validity of quasi-identities is closely linked to solving systems of equations. For systems of equations over finite algebras with finitely many fundamental operations, a complete P/NPC dichotomy is known, while the situation appears to be more complicated for single equations. The complexity of checking the validity of a quasi-identity lies between the complexity of term equivalence (checking whether two terms induce the same function) and the complexity of solving systems of polynomial equations. We prove that for each finite algebra with a Mal'cev term and finitely many fundamental operations, checking the validity of quasi-identities is coNP-complete if the algebra is not abelian, and in P when the algebra is abelian.

BibTeX - Entry

@InProceedings{aichinger_et_al:LIPIcs.STACS.2023.4,
  author =	{Aichinger, Erhard and Gr\"{u}nbacher, Simon},
  title =	{{The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17656},
  URN =		{urn:nbn:de:0030-drops-176560},
  doi =		{10.4230/LIPIcs.STACS.2023.4},
  annote =	{Keywords: quasi-identities, conditional identities, systems of equations}
}

Keywords: quasi-identities, conditional identities, systems of equations
Collection: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Issue Date: 2023
Date of publication: 03.03.2023

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