论文标题
方程可解决的组满意度
Equation satisfiability in solvable groups
论文作者
论文摘要
Goldmann和Russell（2002）启动了对有限群体中方程可满足性问题的复杂性的研究，他们表明该问题在Nilpotent组的多项式时间内，而对于不可溶解的群体来说是NP的完整时间。从那时起，似乎有几个结果表明，在某些可解决的组中，可以在多项式时间内解决该问题的$ g $，其中具有nilpotent的正常亚组$ h $，而nilpotent因子$ g/h $。本文表明，除非指数时间假设失败，否则在多项式时间内具有公式可求解的每个有限群中必须存在的正常亚组。
The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell (2002) where they showed that this problem is in polynomial time 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 normal subgroup must exist in each finite group with equation satisfiability solvable in polynomial time, unless the Exponential Time Hypothesis fails.
