Optimal Inapproximability of Generalized Linear Equations over a Finite Group
2026-05-11 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study a special type of puzzle where you assign values to variables to satisfy as many local rules as possible. These rules are based on combining values over a finite group, like adding numbers or multiplying group elements, and checking if the result lies within a certain set. They provide an algorithm that gets close to the best solution when the puzzle can be perfectly solved and prove that this is the best possible for some cases, assuming P does not equal NP. Their work identifies a rare type of constraint that is hard to approximate in almost perfect cases but still permits a useful approximation when fully solvable.
Constraint Satisfaction Problems (CSPs)Finite GroupApproximation AlgorithmNP-hardnessSatisfiable InstancesApproximation ResistanceP vs NPGeneralized Linear EquationsLocal Constraints
Authors
Amey Bhangale, Yezhou Zhang
Abstract
Constraint satisfaction problems (CSPs) consist of a set of variables taking values from some finite domain and a set of local constraints on these variables. The objective is to find an assignment to the variables that maximizes the fraction of satisfied constraints. In this work, we study the CSP where the constraints are generalized linear equations over a finite group G. More specifically, for a given $S \subseteq G$, the constraints in this CSP are of the form addition of the values to the variables (similarly, product for non-abelian groups), belonging to the set $S$. We give an approximation algorithm for this problem on satisfiable instances and show that it is optimal for certain $S$ assuming $P\neq NP$. This natural predicate is one of the very few known predicates that are approximation resistant on almost satisfiable instances, assuming $P\neq NP$, but admits a non-trivial approximation algorithm on satisfiable instances.