Search

Abstract: An equation over a group is an expression of form , where each is either a variable, an inverted variable, or a group constant and denotes the identity element; such an equation is satisfiable if there is a setting of the variables to values in such that the equality is realized (Engebretsen et al. (2002) ). In this paper, we study the problem of simultaneously satisfying a family of equations over an infinite group . Let EQ G [k] denote the problem of determining the maximum number of simultaneously satisfiable equations in which each equation has occurrences of exactly different variables. When is an infinite cyclic group, we show that it is NP-hard to approximate EQ1 G [3] to within , where EQ1 G [3] denotes the special case of EQ G [3] in which a variable may only appear once in each equation; it is NP-hard to approximate EQ1 G [2] to within ; it is NP-hard to approximate the maximum number of simultaneously satisfiable equations of degree at most to within for any ; for any , it is NP-hard to approximate EQ G [k] within any constant factor. These results extend Håstad’s results (Håstad (2001) ) and results of (Engebretsen et al. (2002) ), who established the inapproximability results for equations over finite Abelian groups and any finite groups respectively. [Copyright &y& Elsevier]