Erhard Aichinger, Simon Grünbacher,
"The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term"
, in Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), Serie Leibniz International Proceedings in Informatics (LIPIcs), Vol. 254, Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik, Dagstuhl, Germany, Seite(n) 4:1--4:12, 3-2023, ISBN: 978-3-95977-266-2
Original Titel:
The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term
Sprache des Titels:
Englisch
Original Buchtitel:
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Original Kurzfassung:
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 \emph{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 $\mathrm{P}/\mathrm{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 $\PP$ when the algebra is abelian.
Sprache der Kurzfassung:
Englisch
Veröffentlicher:
Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
Verlagsanschrift:
Dagstuhl, Germany
Serie:
Leibniz International Proceedings in Informatics (LIPIcs)
Forschungs-