MarriageTheoremのこと

_ IACR ePrint 2013/431まで確認済み、ECCC 2002年分まで確認済み

_ 気になった論文：Inapproximability Results for Equations over Finite Groups, Lars Engebretsen, Jonas Holmerin, Alexander Russell, http://eccc.hpi-web.de/report/2002/030/

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.