Revision #1 Authors: Lars Engebretsen, Jonas Holmerin, Alexander Russell

Accepted on: 3rd December 2002 00:00

Downloads: 959

Keywords:

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.

TR02-030 Authors: Lars Engebretsen, Jonas Holmerin, Alexander Russell

Publication: 5th June 2002 09:17

Downloads: 920

Keywords:

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.