DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2018.17

Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras

Authors: Pawel M. Idziak, Piotr Kawalek, and Jacek Krzaczkowski

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract

Satisfiability of Boolean circuits is NP-complete in general but becomes polynomial time when restricted for example either to monotone gates or linear gates. We go outside Boolean realm and consider circuits built of any fixed set of gates on an arbitrary large finite domain. From the complexity point of view this is connected with solving equations over finite algebras. This in turn is one of the oldest and well-known mathematical problems which for centuries was the driving force of research in algebra. Let us only mention Galois theory, Gaussian elimination or Diophantine Equations. The last problem has been shown to be undecidable, however in finite realms such problems are obviously decidable in nondeterministic polynomial time. A project of characterizing finite algebras m A with polynomial time algorithms deciding satisfiability of circuits over m A has been undertaken in [Pawel M. Idziak and Jacek Krzaczkowski, 2018]. Unfortunately that paper leaves a gap for nilpotent but not supernilpotent algebras. In this paper we discuss possible attacks on filling this gap.

Cite as

Pawel M. Idziak, Piotr Kawalek, and Jacek Krzaczkowski. Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{idziak_et_al:LIPIcs.MFCS.2018.17,
  author =	{Idziak, Pawel M. and Kawalek, Piotr and Krzaczkowski, Jacek},
  title =	{{Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.17},
  URN =		{urn:nbn:de:0030-drops-95993},
  doi =		{10.4230/LIPIcs.MFCS.2018.17},
  annote =	{Keywords: circuit satisfiability, solving equations, Constraint Satisfaction Problem, structure theory}
}

Search Results

Documents authored by Idziak, Pawel M.

Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras

Abstract

Cite as

Thanks for your feedback!

Could not send message