论文标题
方程在指数时间假设下的有限溶液组的硬度
Hardness of equations over finite solvable groups under the exponential time hypothesis
论文作者
论文摘要
Goldmann and Russell（2002）通过证明它在NILPOTENT组的P中启动了方程式令人满意问题的复杂性，而对于不可溶解的群体来说，它在NP群中为NP。从那时起，似乎似乎有几个结果表明，在某些拟合长度二的可解决方案组中，可以在多项式时间内解决该问题。在这项工作中，我们介绍了有限解决组中方程满足问题的第一个下限：在指数时间假设的假设下，我们表明，对于任何拟合长度至少四个，对于某些拟合长度的某些拟合长度三。此外，相同的硬度结果适用于方程身份问题。
Goldmann and Russell (2002) initiated the study of the complexity of the equation satisfiability problem in finite groups by showing that it 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 of Fitting length two. In this work, we present the first lower bounds for the equation satisfiability problem in finite solvable groups: under the assumption of the exponential time hypothesis, we show that it cannot be in P for any group of Fitting length at least four and for certain groups of Fitting length three. Moreover, the same hardness result applies to the equation identity problem.
