On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras

Peter Mayr

doi:10.4230/LIPIcs.MFCS.2023.66

On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras

Peter Mayr

Institute for Algebra

Research output: Chapter in Book/Report/Conference proceeding › Conference proceedings › peer-review

Abstract

For a fixed finite algebra A, we consider the decision problem SysTerm(A): does a given system of term equations have a solution in A? This is equivalent to a constraint satisfaction problem (CSP) for a relational structure whose relations are the graphs of the basic operations of A. From the complexity dichotomy for CSP over fixed finite templates due to Bulatov [4] and Zhuk [18], it follows that SysTerm(A) for a finite algebra A is in P if A has a not necessarily idempotent Taylor polymorphism and is NP-complete otherwise. More explicitly, we show that for a finite algebra A in a congruence modular variety (e.g. for a quasigroup), SysTerm(A) is in P if the core of A is abelian and is NP-complete otherwise. Given A by the graphs of its basic operations, we show that this condition for tractability can be decided in quasi-polynomial time.

Original language	English
Title of host publication	48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Editors	Jerome Leroux, Sylvain Lombardy, David Peleg
Place of Publication	Dagstuhl, Germany
Publisher	Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
Pages	66:1-66:12
Number of pages	12
Volume	272
ISBN (Electronic)	9783959772921
DOIs	https://doi.org/10.4230/LIPIcs.MFCS.2023.66
Publication status	Published - Aug 2023

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	272
ISSN (Print)	1868-8969

Fields of science

101 Mathematics
101001 Algebra
101005 Computer algebra
101013 Mathematical logic
102031 Theoretical computer science

JKU Focus areas

Digital Transformation

Access to Document

10.4230/LIPIcs.MFCS.2023.66

Cite this

Mayr, P. (2023). On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras. In J. Leroux, S. Lombardy, & D. Peleg (Eds.), 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (Vol. 272, pp. 66:1-66:12). Article 66 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 272). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany. https://doi.org/10.4230/LIPIcs.MFCS.2023.66

Mayr, Peter. / On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras. 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). editor / Jerome Leroux ; Sylvain Lombardy ; David Peleg. Vol. 272 Dagstuhl, Germany : Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany, 2023. pp. 66:1-66:12 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{5046d5879d414e2bb5529dde6cdac5cb,

title = "On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras",

abstract = "For a fixed finite algebra A, we consider the decision problem SysTerm(A): does a given system of term equations have a solution in A? This is equivalent to a constraint satisfaction problem (CSP) for a relational structure whose relations are the graphs of the basic operations of A. From the complexity dichotomy for CSP over fixed finite templates due to Bulatov [4] and Zhuk [18], it follows that SysTerm(A) for a finite algebra A is in P if A has a not necessarily idempotent Taylor polymorphism and is NP-complete otherwise. More explicitly, we show that for a finite algebra A in a congruence modular variety (e.g. for a quasigroup), SysTerm(A) is in P if the core of A is abelian and is NP-complete otherwise. Given A by the graphs of its basic operations, we show that this condition for tractability can be decided in quasi-polynomial time.",

author = "Peter Mayr",

year = "2023",

month = aug,

doi = "10.4230/LIPIcs.MFCS.2023.66",

language = "English",

volume = "272",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik, Dagstuhl Publishing, Germany",

pages = "66:1--66:12",

editor = "Jerome Leroux and Sylvain Lombardy and David Peleg",

booktitle = "48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)",

}

Mayr, P 2023, On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras. in J Leroux, S Lombardy & D Peleg (eds), 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). vol. 272, 66, Leibniz International Proceedings in Informatics, LIPIcs, vol. 272, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany, Dagstuhl, Germany, pp. 66:1-66:12. https://doi.org/10.4230/LIPIcs.MFCS.2023.66

On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras. / Mayr, Peter.
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). ed. / Jerome Leroux; Sylvain Lombardy; David Peleg. Vol. 272 Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany, 2023. p. 66:1-66:12 66 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 272).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceedings › peer-review

TY - GEN

T1 - On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras

AU - Mayr, Peter

PY - 2023/8

Y1 - 2023/8

N2 - For a fixed finite algebra A, we consider the decision problem SysTerm(A): does a given system of term equations have a solution in A? This is equivalent to a constraint satisfaction problem (CSP) for a relational structure whose relations are the graphs of the basic operations of A. From the complexity dichotomy for CSP over fixed finite templates due to Bulatov [4] and Zhuk [18], it follows that SysTerm(A) for a finite algebra A is in P if A has a not necessarily idempotent Taylor polymorphism and is NP-complete otherwise. More explicitly, we show that for a finite algebra A in a congruence modular variety (e.g. for a quasigroup), SysTerm(A) is in P if the core of A is abelian and is NP-complete otherwise. Given A by the graphs of its basic operations, we show that this condition for tractability can be decided in quasi-polynomial time.

AB - For a fixed finite algebra A, we consider the decision problem SysTerm(A): does a given system of term equations have a solution in A? This is equivalent to a constraint satisfaction problem (CSP) for a relational structure whose relations are the graphs of the basic operations of A. From the complexity dichotomy for CSP over fixed finite templates due to Bulatov [4] and Zhuk [18], it follows that SysTerm(A) for a finite algebra A is in P if A has a not necessarily idempotent Taylor polymorphism and is NP-complete otherwise. More explicitly, we show that for a finite algebra A in a congruence modular variety (e.g. for a quasigroup), SysTerm(A) is in P if the core of A is abelian and is NP-complete otherwise. Given A by the graphs of its basic operations, we show that this condition for tractability can be decided in quasi-polynomial time.

UR - https://www.scopus.com/pages/publications/85171473122

U2 - 10.4230/LIPIcs.MFCS.2023.66

DO - 10.4230/LIPIcs.MFCS.2023.66

M3 - Conference proceedings

VL - 272

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 66:1-66:12

BT - 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

A2 - Leroux, Jerome

A2 - Lombardy, Sylvain

A2 - Peleg, David

PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

CY - Dagstuhl, Germany

ER -

Mayr P. On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras. In Leroux J, Lombardy S, Peleg D, editors, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Vol. 272. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany. 2023. p. 66:1-66:12. 66. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.MFCS.2023.66

On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras

Abstract

Publication series

Fields of science

JKU Focus areas

Access to Document

Other files and links

Equations in universal algebra

Cite this

On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras

Abstract

Publication series

Fields of science

JKU Focus areas

Access to Document

Other files and links

Projects

Equations in universal algebra

Cite this