2026-07-23T22:21:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11016 2024-03-06T10:47:03Z ddc:004 open_access

Solving Systems of Equations in Supernilpotent Algebras Aichinger, Erhard Supernilpotent algebras polynomial equations polynomial mappings circuit satisfiability 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árolyi and C. Szabó 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erhard Aichinger 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.72 urn:nbn:de:0030-drops-110162 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.72 eng https://creativecommons.org/licenses/by/3.0/legalcode