Browsing by Author "Idziak, Paweł"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • Thumbnail Image
    ItemOpen Access
    Equation satisfiability in solvable groups
    (2022) Idziak, Paweł; Kawałek, Piotr; Krzaczkowski, Jacek; Weiß, Armin
    The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell in (Inf. Comput. 178 (1), 253-262, 10 ) where they showed that this problem is in P for nilpotent groups while it is NP -complete for non-solvable groups. Since then, several results have appeared showing that the problem can be solved in polynomial time in certain solvable groups G having a nilpotent normal subgroup H with nilpotent factor G / H . This paper shows that such a normal subgroup must exist in each finite group with equation satisfiability solvable in polynomial time, unless the Exponential Time Hypothesis fails.