Even faster algorithms for CSATOver supernilpotent algebras

doi:10.4230/LIPIcs.MFCS.2020.55

Even faster algorithms for CSATOver supernilpotent algebras

Communities & Collections

pcg.skipToMenu

Even faster algorithms for CSATOver supernilpotent algebras

View Usage Statistics

Bibliographic description

title:	Even faster algorithms for CSATOver supernilpotent algebras
author:	Kawałek Piotr , Krzaczkowski Jacek
book title:	45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
date of publication :	2020
place of publication : name of publisher:	Schloss Dagstuhl : Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
pages:	55:1-55:13
series:	Leibniz International Proceedings in Informatics, ISSN 1868-8969, eISSN 1868-8969; 170
DOI:	10.4230/LIPIcs.MFCS.2020.55
language:	English
book language:	English
abstract in English:	Recently, a few papers considering the polynomial equation satisfiability problem and the circuitsatisfiability problem over finite supernilpotent algebras from so called congruence modular varietieswere published. All the algorithms considered in these papers are quite similar and rely on checkinga not too big set of potential solutions. Two of these algorithms achieving the lowest time complexityup to now, were presented in [1] (algorithm working for finite supernilpotent algebras) and in [5](algorithm working in the group case). In this paper we show a deterministic algorithm of the sametype solving the considered problems for finite supernilpotent algebras which has lower computationalcomplexity than the algorithm presented in [1] and in most cases even lower than the group casealgorithm from [5]. 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 [17], isthe very first attempt to solving the circuit satisfiability problem using probabilistic algorithms.
keywords in English:	circuit satisfiability, olving equations, supernilpotent algebras, satisfiability in groups
conference:	45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020); 2020-08-24; 2020-08-28; Praga; Republika Czeska; ; ; ; MFCS
affiliation:	Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej, Wydział Matematyki i Informatyki
type:	chapter
subtype:	conference proceedings