DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2023.66

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

Authors: Peter Mayr

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract

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

Cite as

Peter Mayr. On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 66:1-66:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mayr:LIPIcs.MFCS.2023.66,
  author =	{Mayr, Peter},
  title =	{{On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{66:1--66:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.66},
  URN =		{urn:nbn:de:0030-drops-186007},
  doi =		{10.4230/LIPIcs.MFCS.2023.66},
  annote =	{Keywords: systems of equations, general algebras, constraint satisfaction}
}

Document

DOI: 10.4230/LIPIcs.CSL.2016.15

Quantified Constraint Satisfaction on Monoids

Authors: Hubie Chen and Peter Mayr

Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Abstract

We contribute to a research program that aims to classify, for each finite structure, the computational complexity of the quantified constraint satisfaction problem on the structure. Employing an established algebraic viewpoint to studying this problem family, whereby this classification program can be phrased as a classification of algebras, we give a complete classification of all finite monoids.

Cite as

Hubie Chen and Peter Mayr. Quantified Constraint Satisfaction on Monoids. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CSL.2016.15,
  author =	{Chen, Hubie and Mayr, Peter},
  title =	{{Quantified Constraint Satisfaction on Monoids}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Talbot, Jean-Marc and Regnier, Laurent},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.15},
  URN =		{urn:nbn:de:0030-drops-65553},
  doi =		{10.4230/LIPIcs.CSL.2016.15},
  annote =	{Keywords: quantified constraint satisfaction, universal algebra, computational complexity}
}

Search Results

Documents authored by Mayr, Peter

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

Abstract

Cite as

Quantified Constraint Satisfaction on Monoids

Abstract

Cite as

Thanks for your feedback!

Could not send message