License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.55
URN: urn:nbn:de:0030-drops-127225
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12722/
Go to the corresponding LIPIcs Volume Portal

Kawałek, Piotr ; Krzaczkowski, Jacek

Even Faster Algorithms for CSAT Over supernilpotent Algebras

pdf-format:
LIPIcs-MFCS-2020-55.pdf (0.5 MB)

Abstract

Recently, a few papers considering the polynomial equation satisfiability problem and the circuit satisfiability problem over finite supernilpotent algebras from so called congruence modular varieties were published. All the algorithms considered in these papers are quite similar and rely on checking a not too big set of potential solutions. Two of these algorithms achieving the lowest time complexity up to now, were presented in [Aichinger, 2019] (algorithm working for finite supernilpotent algebras) and in [Földvári, 2018] (algorithm working in the group case). In this paper we show a deterministic algorithm of the same type solving the considered problems for finite supernilpotent algebras which has lower computational complexity than the algorithm presented in [Aichinger, 2019] and in most cases even lower than the group case algorithm from [Földvári, 2018]. We also present a linear time Monte Carlo algorithm solving the same problem. This, together with the algorithm for nilpotent but not supernilpotent algebras presented in [Paweł M. Idziak et al., 2020], is the very first attempt to solving the circuit satisfiability problem using probabilistic algorithms.

BibTeX - Entry

@InProceedings{kawaek_et_al:LIPIcs:2020:12722,
  author =	{Piotr Kawa{\l}ek and Jacek Krzaczkowski},
  title =	{{Even Faster Algorithms for CSAT Over supernilpotent Algebras}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12722},
  URN =		{urn:nbn:de:0030-drops-127225},
  doi =		{10.4230/LIPIcs.MFCS.2020.55},
  annote =	{Keywords: circuit satisfiability, solving equations, supernilpotent algebras, satisfiability in groups}
}

Keywords: circuit satisfiability, solving equations, supernilpotent algebras, satisfiability in groups
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI