Erhard Aichinger,
"Solving Systems of Equations in Supernilpotent Algebras"
, in Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), Serie Leibniz International Proceedings in Informatics (LIPIcs), Vol. 138, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Seite(n) 72:1-72:9, 2019, ISBN: 978-3-95977-117-7
Original Titel:
Solving Systems of Equations in Supernilpotent Algebras
Sprache des Titels:
Englisch
Original Buchtitel:
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Original Kurzfassung:
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 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.
Sprache der Kurzfassung:
Englisch
Veröffentlicher:
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Verlagsanschrift:
Dagstuhl, Germany
Serie:
Leibniz International Proceedings in Informatics (LIPIcs)
Forschungs-