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