𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Inapproximability results for equations over finite groups

✍ Scribed by Lars Engebretsen; Jonas Holmerin; Alexander Russell

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
362 KB
Volume
312
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

An equation over a ΓΏnite group G is an expression of form w1w2 : : : w k = 1G, where each wi is a variable, an inverted variable, or a constant from G; such an equation is satisΓΏable 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 ΓΏnite group G and show that it is NP-hard to approximate the number of simultaneously satisΓΏable equations to within |G|for any ΒΏ 0. This generalizes results of H astad (J. ACM 48 (4) (2001) 798), who established similar bounds under the added condition that the group G is Abelian.

πŸ“œ SIMILAR VOLUMES

Computing zeta functions for ordinary fo
Computing zeta functions for ordinary formal groups over finite fields
✍ Takakazu Satoh; Yuichiro Taguchi πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 181 KB

We describe an algorithm to compute the one-dimensional part of the zeta function ZG of an ordinary formal group law G of ΓΏnite dimension d over a ΓΏnite ΓΏeld of p N elements and evaluate its time computational complexity. Assume G is given as d formal power series in 2d variables. Our algorithm comp

A complete set of invariants for finite
A complete set of invariants for finite groups and other results
✍ Moshe Roitman πŸ“‚ Article πŸ“… 1981 πŸ› Elsevier Science 🌐 English βš– 448 KB

For a finite group G and a set Z c ( 1,2,..., n) let e,h 1) = C h(g) 0 et(g) 63 a.. 0 e,(g), SEG where G?) = g if i E I, a?) = 1 if i&Z. We prove, among other results, that the positive integers tr(e,(n, I, ) + ... + e,(n, I,))': n, r, k) 1, Zjz { l,..., n), 1 < II,1 < 3 for 1 1 and a set Z s { 1,2