Name
Abstract | ||
|---|---|---|
Recently, M. Kompatscher proved that for each finite supernilpotent algebra $mathbf{A}$ 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 $mathbf{A}$, and let [ d := |A|^{log_2 (mu) + log_2 (|A|) + 1}.] Applying a method that G. Ku0027{a}rolyi and C. Szabu0027{o} had used to solve equations over finite nilpotent rings, we show that for $mathbf{A}$, there is $c in mathbb{N}$ such that a solution of every system of $s$ equations $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. |
Year | Venue | DocType |
|---|---|---|
2019 | MFCS | Conference |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erhard Aichinger | 1 | 2 | 2.92 |