License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.72
URN: urn:nbn:de:0030-drops-110162
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11016/
Go to the corresponding LIPIcs Volume Portal

Aichinger, Erhard

Solving Systems of Equations in Supernilpotent Algebras

pdf-format:
LIPIcs-MFCS-2019-72.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{aichinger:LIPIcs:2019:11016,
  author =	{Erhard Aichinger},
  title =	{{Solving Systems of Equations in Supernilpotent Algebras}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{72:1--72:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11016},
  URN =		{urn:nbn:de:0030-drops-110162},
  doi =		{10.4230/LIPIcs.MFCS.2019.72},
  annote =	{Keywords: Supernilpotent algebras, polynomial equations, polynomial mappings, circuit satisfiability}
}

Keywords: Supernilpotent algebras, polynomial equations, polynomial mappings, circuit satisfiability
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI