Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR02-030 | 3rd December 2002 00:00

Inapproximability Results for Equations over Finite Groups

RSS-Feed




Revision #1
Authors: Lars Engebretsen, Jonas Holmerin, Alexander Russell
Accepted on: 3rd December 2002 00:00
Downloads: 940
Keywords: 


Abstract:

Abstract: 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 Håstad (2001, J.ACM, 48(4)), who
established similar bounds under the added condition that the
group G is Abelian.


Paper:

TR02-030 | 3rd June 2002 00:00

Inapproximability Results for Equations over Finite Groups


Abstract:

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 Håstad (2001, J.ACM, 48(4)), who
established similar bounds under the added condition that the
group G is Abelian.



ISSN 1433-8092 | Imprint