Search

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.