Solving systems of equations in supernilpotent algebras

DOI10.4230/LIPICS.MFCS.2019.72arXiv1901.07862MaRDI QIDQ6312913FDOQ6312913

Erhard Aichinger

Publication date: 23 January 2019

Abstract: Recently, M. Kompatscher proved that for each finite supernilpotent algebra $mathbfA$ in a congruence modular variety, there is a polynomial time algorithm to solve polynomial equations over this algebra. Let $mu$ be the maximal arity of the fundamental operations of $mathbfA$, and let [ d := |A|^{log_2 (mu) + log_2 (|A|) + 1}.] Applying a method that G. K'{a}rolyi and C. Szab'{o} had used to solve equations over finite nilpotent rings, we show that for $mathbfA$, there is $cinmathbbN$ such that a solution of every system of $s$ equations in $n$ variables can be found by testing at most $c{n}^{sd}$ (instead of all $|A{|}^n$ possible) assignments to the variables. This also yields new information on some circuit satisfiability problems.

Mathematics Subject Classification ID

Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70)

This page was built for publication: Solving systems of equations in supernilpotent algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6312913)