2026-07-26T16:45:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16468 2024-03-06T10:57:34Z ddc:004 open_access

Satisfiability Problems for Finite Groups Idziak, Paweł M. Kawałek, Piotr Krzaczkowski, Jacek Weiß, Armin Satisifiability Solvable groups ProgramSat PolSat Exponential Time Hypothesis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paweł M. Idziak and Piotr Kawałek and Jacek Krzaczkowski and Armin Weiß 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.127 urn:nbn:de:0030-drops-164685 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.127 eng https://creativecommons.org/licenses/by/4.0/legalcode