Name
Abstract | ||
|---|---|---|
An equation over a group G is an expression of form w"1...w"k=1"G, where each w"i is either a variable, an inverted variable, or a group constant and 1"G denotes the identity element; such an equation is satisfiable if there is a setting of the variables to values in G such that the equality is realized (Engebretsen et al. (2002) [10]). In this paper, we study the problem of simultaneously satisfying a family of equations over an infinite group G. Let EQ"G[k] denote the problem of determining the maximum number of simultaneously satisfiable equations in which each equation has occurrences of exactly k different variables. When G is an infinite cyclic group, we show that it is NP-hard to approximate EQ^1"G[3] to within 48/47-@e, where EQ^1"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 EQ^1"G[2] to within 30/29-@e; it is NP-hard to approximate the maximum number of simultaneously satisfiable equations of degree at most d to within d-@e for any @e; for any k=4, it is NP-hard to approximate EQ"G[k] within any constant factor. These results extend Hastad's results (Hastad (2001) [17]) and results of (Engebretsen et al. (2002) [10]), who established the inapproximability results for equations over finite Abelian groups and any finite groups respectively. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.tcs.2010.03.010 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Cyclic groups,Computational complexity,finite Abelian group,group G,satisfiable equation,infinite cyclic group,NP-hardness,Groups,k different variable,infinite group,approximate EQ,Infinite groups,Inapproximability result,inverted variable,Approximation,maximum number,Probabilistically checkable proofs,Optimization,finite group | Journal | 411 |
Issue | ISSN | Citations |
26-28 | Theoretical Computer Science | 0 |
PageRank | References | Authors |
0.34 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenbin Chen | 1 | 4 | 2.19 |
| Dengpan Yin | 2 | 46 | 3.64 |
| Zhengzhang Chen | 3 | 198 | 25.62 |