2026-07-20T05:40:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17656 2024-03-06T11:00:13Z ddc:004 open_access

The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term Aichinger, Erhard Grünbacher, Simon quasi-identities conditional identities systems of equations 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erhard Aichinger and Simon Grünbacher 2023 Is Part Of LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2023.4 urn:nbn:de:0030-drops-176560 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.4 eng https://creativecommons.org/licenses/by/4.0/legalcode