ECCC-Report TR02-030https://eccc.weizmann.ac.il/report/2002/030Comments and Revisions published for TR02-030en-usTue, 03 Dec 2002 00:00:00 +0200
Revision 1
| Inapproximability Results for Equations over Finite Groups |
Lars Engebretsen,
Jonas Holmerin,
Alexander Russell
https://eccc.weizmann.ac.il/report/2002/030#revision1Abstract: 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.
Tue, 03 Dec 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/2002/030#revision1
Paper TR02-030
| Inapproximability Results for Equations over Finite Groups |
Lars Engebretsen,
Jonas Holmerin,
Alexander Russell
https://eccc.weizmann.ac.il/report/2002/030An 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.
Wed, 05 Jun 2002 09:17:51 +0300https://eccc.weizmann.ac.il/report/2002/030