Solving equations in supernilpotent algebras

Description

Recently, M.\ Kompatscher proved that for each finite supernilpotent algebra $A$ 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 $A$, 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 $A$, there is $c \in \N$ such that a solution of every equation in $n$ variablescan be found by testing at most $c n^{d}$ (instead of all $|A|^n$ possible) assignments to the variables. We also consider systems of equations over such algebras.

Period	23 Nov 2018
Event title	unbekannt/unknown
Event type	Other
Location	ItalyShow on map