The complexity of checking quasi-identities over finite algebras with a Mal'cev term
Sprache des Vortragstitels:
Englisch
Original Tagungtitel:
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Sprache des Tagungstitel:
Englisch
Original Kurzfassung:
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 (joint work with Erhard Aichinger).
Forschungs-