Search Results

Documents authored by Kawałek, Piotr

Document
DOI: 10.4230/LIPIcs.STACS.2024.45
Circuit Equivalence in 2-Nilpotent Algebras

Authors: Piotr Kawałek, Michael Kompatscher, and Jacek Krzaczkowski

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The circuit equivalence problem Ceqv(A) of a finite algebra A is the problem of deciding whether two circuits over A compute the same function or not. This problem not only generalises the equivalence problem for Boolean circuits, but is also of interest in universal algebra, as it models the problem of checking identities in A. In this paper we prove that Ceqv(A) ∈ 𝖯, if A is a finite 2-nilpotent algebra from a congruence modular variety.
Cite as

Piotr Kawałek, Michael Kompatscher, and Jacek Krzaczkowski. Circuit Equivalence in 2-Nilpotent Algebras. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 45:1-45:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kawalek_et_al:LIPIcs.STACS.2024.45,
  author =	{Kawa{\l}ek, Piotr and Kompatscher, Michael and Krzaczkowski, Jacek},
  title =	{{Circuit Equivalence in 2-Nilpotent Algebras}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{45:1--45:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.45},
  URN =		{urn:nbn:de:0030-drops-197554},
  doi =		{10.4230/LIPIcs.STACS.2024.45},
  annote =	{Keywords: circuit equivalence, identity checking, nilpotent algebra}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.127
Satisfiability Problems for Finite Groups

Authors: Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, and Armin Weiß

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Over twenty years ago, Goldmann and Russell initiated the study of the complexity of the equation satisfiability problem (PolSat and the NUDFA program satisfiability problem (ProgramSat) in finite groups. They showed that these problems are in 𝖯 for nilpotent groups while they are NP-complete for non-solvable groups. In this work we completely characterize finite groups for which the problem ProgramSat can be solved in randomized polynomial time under the assumptions of the Randomized Exponential Time Hypothesis and the Constant Degree Hypothesis. We also determine the complexity of PolSat for a wide class of finite groups. As a by-product, we obtain a classification for ListPolSat, a version of PolSat where each variable can be restricted to an arbitrary subset. Finally, we also prove unconditional algorithms for these problems in certain cases.
Cite as

Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, and Armin Weiß. Satisfiability Problems for Finite Groups. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 127:1-127:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{idziak_et_al:LIPIcs.ICALP.2022.127,
  author =	{Idziak, Pawe{\l} M. and Kawa{\l}ek, Piotr and Krzaczkowski, Jacek and Wei{\ss}, Armin},
  title =	{{Satisfiability Problems for Finite Groups}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{127:1--127:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.127},
  URN =		{urn:nbn:de:0030-drops-164685},
  doi =		{10.4230/LIPIcs.ICALP.2022.127},
  annote =	{Keywords: Satisifiability, Solvable groups, ProgramSat, PolSat, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.37
Satisfiability of Circuits and Equations over Finite Malcev Algebras

Authors: Paweł M. Idziak, Piotr Kawałek, and Jacek Krzaczkowski

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We show that the satisfiability of circuits over finite Malcev algebra A is NP-complete or A is nilpotent. This strengthens the result from our earlier paper [Idziak and Krzaczkowski, 2018] where nilpotency has been enforced, however with the use of a stronger assumption that no homomorphic image of A has NP-complete circuits satisfiability. Our methods are moreover strong enough to extend our result of [Idziak et al., 2021] from groups to Malcev algebras. Namely we show that tractability of checking if an equation over such an algebra A has a solution enforces its nice structure: A must have a nilpotent congruence ν such that also the quotient algebra A/ν is nilpotent. Otherwise, if A has no such congruence ν then the Exponential Time Hypothesis yields a quasipolynomial lower bound. Both our results contain important steps towards a full characterization of finite algebras with tractable circuit satisfiability as well as equation satisfiability.
Cite as

Paweł M. Idziak, Piotr Kawałek, and Jacek Krzaczkowski. Satisfiability of Circuits and Equations over Finite Malcev Algebras. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{idziak_et_al:LIPIcs.STACS.2022.37,
  author =	{Idziak, Pawe{\l} M. and Kawa{\l}ek, Piotr and Krzaczkowski, Jacek},
  title =	{{Satisfiability of Circuits and Equations over Finite Malcev Algebras}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.37},
  URN =		{urn:nbn:de:0030-drops-158474},
  doi =		{10.4230/LIPIcs.STACS.2022.37},
  annote =	{Keywords: Circuit satisfiability, solving equations, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.55
Even Faster Algorithms for CSAT Over supernilpotent Algebras

Authors: Piotr Kawałek and Jacek Krzaczkowski

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Recently, a few papers considering the polynomial equation satisfiability problem and the circuit satisfiability problem over finite supernilpotent algebras from so called congruence modular varieties were published. All the algorithms considered in these papers are quite similar and rely on checking a not too big set of potential solutions. Two of these algorithms achieving the lowest time complexity up to now, were presented in [Aichinger, 2019] (algorithm working for finite supernilpotent algebras) and in [Földvári, 2018] (algorithm working in the group case). In this paper we show a deterministic algorithm of the same type solving the considered problems for finite supernilpotent algebras which has lower computational complexity than the algorithm presented in [Aichinger, 2019] and in most cases even lower than the group case algorithm from [Földvári, 2018]. We also present a linear time Monte Carlo algorithm solving the same problem. This, together with the algorithm for nilpotent but not supernilpotent algebras presented in [Paweł M. Idziak et al., 2020], is the very first attempt to solving the circuit satisfiability problem using probabilistic algorithms.
Cite as

Piotr Kawałek and Jacek Krzaczkowski. Even Faster Algorithms for CSAT Over supernilpotent Algebras. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kawalek_et_al:LIPIcs.MFCS.2020.55,
  author =	{Kawa{\l}ek, Piotr and Krzaczkowski, Jacek},
  title =	{{Even Faster Algorithms for CSAT Over supernilpotent Algebras}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.55},
  URN =		{urn:nbn:de:0030-drops-127225},
  doi =		{10.4230/LIPIcs.MFCS.2020.55},
  annote =	{Keywords: circuit satisfiability, solving equations, supernilpotent algebras, satisfiability in groups}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact