Inapproximability results for equations over finite groups
2004 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 312, no 1, 17-45 p.Article in journal (Refereed) Published
An equation over a finite group G is an expression of form w(1)w(2). . .w(k) = 1(G), where each w(i) is a variable, an inverted variable, or a constant from G; such an equation is satisfiable if there is a setting of the variables to values in G so that the equality is realized. We study the problem of simultaneously satisfying a family of equations over a finite group G and show that it is NP-hard to approximate the number of simultaneously satisfiable equations to within \G\ - epsilon for any epsilon > 0. This generalizes results of Hastad (J. ACM 48 (4) (2001) 798), who established similar bounds under the added condition that the group G is Abelian.
Place, publisher, year, edition, pages
2004. Vol. 312, no 1, 17-45 p.
optimization, approximation, groups, finite groups, probabilistically checkable proofs, NP-hardness
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-43803DOI: 10.1016/S0304-3975(03)00401-8ISI: 000188530600003ScopusID: 2-s2.0-0347024174OAI: oai:DiVA.org:kth-43803DiVA: diva2:448985
QC 201110192011-10-192011-10-182011-10-31Bibliographically approved