Printer Friendly

The extended equivalence and equation solvability problems for groups.

1 Introduction

The algorithmic aspects of the equivalence problem and the equation solvability problem have received increasing attention in the past two decades. The equivalence problem for a finite algebra A asks whether or not two (term or polynomial) expressions s and t are equivalent over A (denoted by A [??] s [approximately equal to] t), i.e. if s and t determine the same function over A. The equation solvability is one of the oldest problems of algebra: it asks whether or not two (term or polynomial) expressions s, t can attain the same value for some substitution over a finite algebra A, i.e. if the equation s = t can be solved. The complexity of the equivalence and equation solvability problems have been thoroughly investigated for finite classical algebras, e.g. for finite rings Burris and Lawrence (1993); Hunt and Stearns (1990); Lawrence and Willard (1997); Szabo and Vortesi (2011), for finite groups Burris and Lawrence (2004); Goldmann and Russell (2002); Horvath (2011); Horvath et al. (2007); Horvath and Szabo (2006), or for finite semigroups and monoids Almeida et al. (2009); Kisielewicz (2004); Klima (2004, 2009); Plescheva and Vortesi (2006); Seif and Szabo (2006). The complexity of these questions is determined with respect to the length of the input term or polynomial expressions.

In many situations a term or polynomial can be expressed in a more concise way using new operations, not only the basic operations of the algebra. For example, the length of [[[[x.sub.1], [x.sub.2]], [x.sub.3]],..., [x.sub.n]] is n if expressed by using the commutator, and is O ([2.sup.n]) if expressed by using the group multiplication. Such a change in the length suggests that the complexity of the equivalence or of the equation solvability problems may change as well. It is indeed the case in some situation: in Horvath and Szabo (2011) it is shown that for the alternating group on four elements these problems have complexity in P; but if the group is extended by the commutator as an extra operation, then the equivalence problem is coNP-complete and the equation solvability problem is NP-complete. Such a complexity change cannot occur for two element algebras Gorazd and Krzaczkowski (2011). To further investigate whether or not additional operations can affect the complexity of the equivalence and equation solvability problems, we introduce their extended version for finite groups.

Definition 1 Let G = (G,x) be a finite group. We say that the extended equivalence (equation solvability) problem over G is in P, if for arbitrary terms [f.sub.1],...,[f.sub.k] the equivalence (equation solvability) problem over (G, x, [f.sub.1],..., [f.sub.k]) is in P. We say that the extended equivalence problem over G is coNP-complete (the equation solvability problem is NP-complete), if there exist terms [f.sub.1],... ,[f.sub.k] such that the equivalence problem over (G, x, [f.sub.1],... ,[f.sub.k]) is coNP-complete (the equation solvability problem over (G, x, [f.sub.1],... ,[f.sub.k]) is NP-complete).

It is clear that the complexity of an extended problem is at least as hard as the original problem. Definition 1 can be extended to arbitrary algebras, e.g. for rings. Considering finite rings and applying the methods described in Burris and Lawrence (1993); Horvath (2011); Hunt and Stearns (1990) one can arrive at a similar dichotomy theorem for the extended problems as for the one about the original problems.

Theorem 2 Let R be a finite ring. If R is nilpotent, then the extended equivalence and extended equation solvability problems can be solved in polynomial time. If R is non-nilpotent, then the extended equivalence problem is coNP-complete, and the extended equation solvability problem is NP-complete.

The main results of this paper are two similar theorems for groups.

Theorem 3 Let G = (G, x) be a finite group. If G is nilpotent, then the equivalence problem over G can be solved in polynomial time. If G is non-nilpotent, then there exists a term f over G such that the equivalence problem over (G, x, f) is coNP-complete.

Theorem 4 Let G = (G, x) be a finite group. If G is nilpotent, then the equation solvability problem over G can be solved in polynomial time. If G is non-nilpotent, then there exists a term f over G such that the equation solvability problem over (G, x, f) is NP-complete.

For non-nilpotent, solvable groups we prove Theorems 3 and 4 by induction. The initial case of the induction is considered in Section 2, then we prove Theorems 3 and 4 in general in Section 3. We finish the paper by mentioning some open problems in Section 4.

2 Abelian normal subgroup

Let G = (G, x) be a finite, solvable, non-nilpotent group. Let us consider the lower central series of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Let us denote by [gamma](G) the normal subgroup in which this decreasing sequence terminates, and let T be the smallest positive integer such that [[gamma].sub.T](G) = [gamma](G). We prove the solvable, non-nilpotent group case of Theorems 3 and 4 by induction on the order of the group. The initial case is where both [gamma](G) and G/[C.sub.G]([gamma](G)) are commutative.

Theorem 5 Let G = (G, x) be a finite, solvable, non-nilpotent group. Assume that the groups [gamma](G) and G/[C.sub.G]([gamma](G)) are commutative. Then there exists a term f such that the equivalence problem over (G, x, f) is coNP-complete, and the equation solvability problem over (G, x, f) is NP-complete.

Proof: We prove that there exists a term f such that the equivalence problem over (G, x, f) is coNP-complete. Let A = [gamma](G) and B = G/[C.sub.G]([gamma](G)). Let End A denote the endomorphism ring of A. The group G acts on A by conjugation. This action of G is isomorphic to B. We identify B with its image in End A. Let [phi]: G [right arrow] B denote the natural homomorphism from G onto B. Let R be the ring generated by B in End A, i.e. R = [(B).sub.End A]. Since B is commutative, R is commutative as well. Moreover 1 [member of] B implies 1 [member of] R. Note that A is a faithful left-module over End A, and therefore it is a faithful module over the commutative ring R.

Denote the action of the ring element r [member of] R on a [member of] A by [a.sup.r]. For example, if a [member of] A, g [member of] G, b = [gamma](g), then [a.sup.1] = a, [a.sup.b] = [a.sup.[phi](g)] = [g.sup.-1]ag, and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Let us denote the set of commutator actions in End A by C: C = {b - 1 | b [member of] B}. Let [R.sub.c] [less than or equal to] End A be the subring of R generated by the commutator actions:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Note, that A is a faithful [R.sub.c]-module, as well. Note that [absolute value of B] = [absolute value of C]. Let c = [absolute value of C], and let d = [absolute value of [R.sub.c]]. Let [J.sub.c] denote the Jacobson radical of [R.sub.c].

We prove the theorem in the following steps.

1. We prove in Lemma 6 that there exists a polynomial p with integer coefficients such that [R.sub.c] = p ([phi] (G)).

2. We prove in Lemma 7 that the ring [R.sub.c] is non-nilpotent, that is [R.sub.c]/[J.sub.c] is a direct sum of finite fields [F.sub.1],..., [F.sub.1]. Assume that [absolute value of [F.sub.1]] [greater than or equal to] xxx [greater than or equal to] [absolute value of [F.sub.l]].

3. Let [q.sub.1] denote the number of elements of [F.sub.1]. We prove in Lemma 8 that [q.sub.1] > 3.

4. We introduce the term f using the polynomial p from Step 1. We polynomially reduce the GRAPH [q.sub.1]-coloring problem to the equivalence problem over (G, x, f). The instance of the GRAPH [q.sub.1]-coloring problem is a graph [GAMMA], and it asks whether or not the vertices of [GAMMA] can be colored by [q.sub.1] colors such that no two adjacent vertices share the same color. This problem is well-known to be NP-complete Karp (1972). For an arbitrary graph [GAMMA] we construct a term expression [t.sub.[GAMMA]] over (G, x, f) such that (G, x, f) = [t.sub.[GAMMA]] [approximately equal to] 1 if and only if the graph [GAMMA] is not [q.sub.1]-colorable. The length of [t.sub.[GAMMA]] will be linear in the size of [GAMMA].

In step 1 we prove that [R.sub.c] is a verbal subring of R.

Lemma 6 There exists a polynomial p with integer coefficients such that [R.sub.c] = p (B) = p ([phi] (G)).

Proof: Let C = {[u.sub.1],... ,[u.sub.c]} and [R.sub.c] = {[r.sub.1],... ,[r.sub.d]}. As [R.sub.c] = [<C>.sub.R], for every [r.sub.i] [member of] [R.sub.c] there exist a polynomial [p.sub.i] with integer coefficients such that [p.sub.i] has no constant coefficient and [r.sub.i] = [p.sub.i] ([u.sub.1],..., [u.sub.c]). For every [r.sub.i] [member of] [R.sub.c] let us fix such a polynomial [p.sub.i]. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Clearly, p (B) [subset or equal to] [R.sub.c]. Let [b.sub.j] = [u.sub.j] + 1 for 1 [less than or equal to] j [less than or equal to] c. Then B = {[b.sub.1],... ,[b.sub.c]}. Let us fix 1 [less than or equal to] i [less than or equal to] d and consider the substitution [x.sub.i,j] = [b.sub.c], [x.sub.l,j] = 1 (l [not equal to] i). For this substitution the value of p is [p.sub.i]([u.sub.1],..., [u.sub.c]) = [r.sub.i] . Hence [r.sub.i] [member of] p (B) yielding [R.sub.c] = p (B) = p ([phi] (G)).

We continue with step 2 of the proof.

Lemma 7 The ring [R.sub.c] is non-nilpotent.

Proof: Let F (G) denote the Fitting subgroup of G, the unique largest nilpotent normal subgroup of G Robinson (1995). As G is non-nilpotent, F (G) [not equal to] G, and F (G) is the set of left-Engel elements Baer (1957). An element g [member of] G is a left-Engel element, if for every h e G there exists a positive integer [k.sub.h], such that the [k.sub.h]-iterated commutator of h by g is the identity element: [[[h, g], g]... g] = 1. Let g [member of] G be arbitrary, and let r = [phi] (g) - 1. We prove that g is a left-Engel element if and only if r is nilpotent.

Assume that g is a left-Engel element. Now, for every h [member of] G there exists a positive integer [k.sub.h], such that the [k.sub.h]-iterated commutator of h by g is the identity element: [[[h,g],g].. .g] = 1. Let k be the maximum of these numbers: k = max {[k.sub.h] | h [member of] G}. Recall that as [gamma](G) [??] G and [gamma](G) is abelian, we have [gamma](G) [subset or equal to] F (G). Then for every a [member of] A we have [[[a, g], g]... g] = 1. By [a, g] = [a.sup.[phi](g)-1] = [a.sup.r] we obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], yielding r.sup.k = 0, i.e. r is nilpotent.

Now, assume that r is nilpotent. Let k be the smallest positive integer such that [r.sub.k] = 0. That is, for every [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], we obtain that the k-iterated commutator of a by g is the identity of G: [[[a, g], g]... g] = 1. Let T be the positive integer for which A = [[gamma].sub.T](G). Let h [member of] G be arbitrary, then the T-iterated commutator of h by g is an element of A: [[[h, g], g]... g] [member of] A. Thus the (T + k)-iterated commutator of h by g is the identity element of G: [[[h, g], g]... g] = 1 Therefore g is a left-Engel element. ?

Let [J.sub.c] denote the Jacobson radical of [R.sub.c]. Now, [R.sub.c]/[J.sub.c] is a direct sum of finite fields (Jacobson, 1945, Theorem 27). In step 3 we prove that at least one of these fields contains more than two elements.

Lemma 8 For the ring [R.sub.c] we have [R.sub.c]/[J.sub.c] = [Z.sup.l.sub.2].

Proof: We prove the lemma indirectly: assume that [R.sub.c]/[J.sub.c] = [Z.sup.l.sub.2] for some positive integer l. Now, ([r.sup.2] + r) [member of] [J.sub.c] for every r [member of] [R.sub.c]. Let t be the smallest positive integer for which [r.sup.t] is idempotent for every r [member of] [R.sub.c] and the exponent of G divides t. Thus [R.sub.c]/[J.sub.c] = [Z.sup.l.sub.2] implies [([r.sup.2] + r).sup.t] = 0 for every r [member of] [R.sub.c]. Let b = [phi] (g) for some g [member of] G \ F (G). In the proof of Lemma 7 it is shown that commuting with g is a non-nilpotent action, that is (b - 1) is non-nilpotent. Let r = (b - 1), then r [member of] [R.sub.c]. Let us calculate the value of [([r.sup.2] + r).sup.t] in the ring R. Since R is a commutative unitalring, [([r.sup.2] + r).sup.2] = [r.sup.2] x [(r + 1).sup.t] = [r.sup.t] x [b.sup.t]. The exponent of G divides t, hence [b.sup.t] = [phi][(g).sup.t] = [phi]([g.sup.t]) = [phi](1) = 1. Thus [([r.sup.2] + r).sup.t] = 0 yields [r.sup.t] = 0, contradicting that r is a non-nilpotent element.

We continue with step 4 of the proof. Let [F.sub.1],..., [F.sub.l] be the fields occurring as a direct summand in [R.sub.c]/[J.sub.c] (with multiplicity), i.e. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. By Lemma 8 we have [q.sub.1] [greater than or equal to] 3. By Lemma 6 we can define the term f. Let p be the polynomial in Lemma 6. The polynomial p depends on dc variables, where c = [absolute value of C], d = [absolute value of [R.sub.c]]. Let [[bar.x].sub.1] and [[bar.x].sub.2] be disjoint vectors of dc variables, that is the set of variables of [[bar.x].sub.1] is disjoint from the set of variables of [[bar.x].sub.2]. Let f be defined in the following way:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1)

Now, f is a term over G and it depends on 2dc + 1 variables. We shall polynomially reduce the GRAPH [q.sub.1] -coloring to the equivalence problem over (G, x, f). By Lemma 8 we have [q.sub.1] [greater than or equal to] 3, thus the GRAPH [q.sub.1]-coloring is NP-complete Karp (1972). Let [GAMMA] = (V, E) be an arbitrary simple graph with no loops. Let V = {[v.sub.1],... ,[v.sub.n]} be its set of vertices and let E = {[e.sub.1],... ,[e.sub.m]} be the set of its edges. Let t be the smallest positive integer such that for every r [member of] [R.sub.c] the element [r.sup.t] is idempotent. In particular, if r [member of] [J.sub.c] then [r.sup.t] = 0. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2)

We would like to express [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] using f defined by (1), where each [z.sub.i] runs through [R.sub.c] and y runs through A. We achieve this in two steps. We construct

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

for disjoint [[bar.x].sub.1],... ,[[bar.x].sub.n] vectors of dc variables, ensuring that the arguments of [u.sub.[GAMMA]] will be in [R.sub.c]. Then we guarantee that the value of y will be in A.

Let [bar.x] denote the vector of all 'x' variables, i.e. [bar.x] = ([[bar.x].sub.1],..., [[bar.x].sub.n]). Now, we want to express W (y, [bar.x]). Although, W is a term over G, its length would be exponential in the size of [GAMMA] using only the group multiplication. We shall express W using f, and thus the length of W will be linear in the size of [GAMMA]. For every edge e = [v.sub.i][v.sub.j] let [w.sub.e] (y, [bar.x]) be the t-times iterated version of f (y, [[bar.x].sub.i], [[bar.x].sub.j]):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Let W (y, [bar.x]) denote the composition of the terms [w.sub.e]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

As A is a verbal normal subgroup of G, there exists a term s ([bar.y]) of variables [bar.y] = ([y.sub.1],... ,[y.sub.k]) such that s (G) = A. Finally, let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (3)

The length of [t.sub.[GAMMA]] is linear in the size of [GAMMA]: for every edge e [member of] E we have [parallel][w.sub.e][parallel] [less than or equal to] 2tcd +1 = O (1). Moreover, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Finally, [parallel][t.sub.[GAMMA]][parallel] [less than or equal to] [parallel]W[parallel] x [parallel]s[parallel] = O (m), as s depends only on G and not on r.

We prove that [GAMMA] is not colorable by [q.sub.1] colors if and only if (G, x, f) [??] [t.sub.[GAMMA]] [approximately equal to] 1. Assume that r is [q.sub.1]-colorable. Color the vertices of [GAMMA] by the elements of [F.sub.1]. Thus there exist elements [r.sub.1],... ,[r.sub.n] [member of] [R.sub.c] such that the color of [v.sub.i] is the [F.sub.1]-component of [r.sub.i]. That is, if if [psi]: [R.sub.c] [right arrow] [F.sub.1] is the natural homomorphism, then [psi]([r.sub.i]) is the color of [v.sub.i]. Now, for every edge [v.sub.i][v.sub.j] the [F.sub.1]-component of ([r.sub.i] - [r.sub.j]) is not 0. Hence [([r.sub.i] - [r.sub.j]).sup.t] = 1 in [F.sub.1] for every edge [v.sub.i][v.sub.j]. That is, the [F.sub.1]-component of [u.sub.[GAMMA]] ([r.sub.1],..., [r.sub.n]) is 1, and [u.sub.[GAMMA]] ([r.sub.1],..., [r.sub.n]) = 0. Therefore there exists an element a [member of] A such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. For every 1 [less than or equal to] i [less than or equal to] n let [[bar.g].sub.i] [member of] [G.sub.dc] such that [r.sub.i] = p ([[bar.g].sub.i]) and let g = ([[bar.g].sub.1],..., [[bar.g].sub.n]). Let [bar.h] [member of] [G.sup.k] such that a = s ([bar.h]). Now,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Assume now, that [GAMMA] is not [q.sub.1]-colorable. Consider an arbitrary substitution of [t.sub.[GAMMA]]. Let [bar.h] [member of] [G.sup.k] be arbitrary and for every 1 [less than or equal to] i [less than or equal to] n let [[bar.g].sub.i] [member of] [G.sup.dc] be arbitrary. Let [bar.g] = ([[bar.g].sub.1],..., [[bar.g].sub.n]). Let a = s ([bar.h]) and let [r.sub.i] = [p.sub.i]([[bar.g].sub.i]). Now, a [member of] A and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

We prove that [u.sub.[GAMMA]] ([r.sub.1],..., [r.sub.n]) = 0. For this substitution, let us define the color of [v.sub.i] to be the [F.sub.1]-component of [r.sub.i]. Since [GAMMA] is not [q.sub.1]-colorable, there exists an edge [v.sub.i][v.sub.j] such that the [F.sub.1]-components of [r.sub.i] and [r.sub.j] are the same. Thus the [F.sub.1]-component of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] is 0. For every 1 [less than or equal to] k [less than have [q.sub.1] [greater than or equal to] [absolute value of [F.sub.k]], i.e. the graph r is not [absolute value of [F.sub.k]]-colorable. Thus, in a similar fashion, it follows that the [F.sub.k]-component of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] is 0, as well. That is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] yielding [u.sub.[GAMMA]] (n,...,[r.sub.n]) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Note that Lemma 8 was used for [q.sub.1] = [absolute value of [F.sub.1]] [greater than or equal to] 3, i.e. the GRAPH [q.sub.1]-coloring is NP-complete.

Finally, we prove that the equation solvability over (G, x, f) is NP-complete. The proof is literally the same as the proof of the coNP-completeness of the equivalence problem, apart from the following differences. Let r [member of] [R.sub.c] be an idempotent such that its [F.sub.1]-component is 1, and its [F.sub.k]-component is 0 (for 2 [less than or equal to] k [less than or equal to] l). If r is [q.sub.1]-colorable then, as we proved in the coNP-completeness part, there exists elements [r.sub.1],... ,[r.sub.n] [member of] [R.sub.c] such that [u.sub.[GAMMA]] ([r.sub.1],..., [r.sub.n]) [not equal to] 0. From the same argument, r x [u.sub.[GAMMA]] ([r.sub.1],... ,[r.sub.n]) = r follows, as well. Let a [member of] A, a [not equal to] 1 be arbitrary for which [a.sup.r] = a. Then [t.sub.[GAMMA]] = a is solvable if and only if r is [q.sub.1]-colorable.

3 Proof of Theorems 3 and 4

In this section we prove Theorems 3 and 4. By the following lemma the equivalence and equation solvability problems can be reduced to verbal subgroups.

Lemma 9 Let V = (V, x) be a verbal subgroup of the group G = (G, x). Let f be a group term.

1. If the equivalence problem over (V, , f) is coNP-complete, then the equivalence problem over (G, x, f) is coNP-complete.

2. If the equation solvability problem over (V, x, f) is NP-complete, then the equation solvability problem over (G, x, f) is NP-complete.

Proof: We prove only (1), as the proof of (2) is similar. We give a polynomial reduction from the equivalence problem of (V, x, f) to the equivalence problem of (G, x, f). For every term t([x.sub.1],..., [x.sub.n]) over (V, x, f) we present a term t' over (G, x, f) such that t [approximately equal to] 1 over (V, x, f) if and only if t' [approximately equal to] 1 over (G, x, f). As V is verbal, there exists a term s([x.sub.1],... ,[x.sub.k]) over G such that s(G) = V. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

While [[bar.y].sub.i] runs through all the k-tuples of G, the value of s ([[bar.y].sub.i]) attains every element of V. Thus if t [not equal to] 1 at some evaluation ([h.sub.1],... ,[h.sub.n]) [member of] [V.sup.n], then we can choose the tuples [[bar.y].sub.i] such that s([[bar.y].sub.i]) = [h.sub.i]. Thus there exists an evaluation of t' such that t' [not equal to] 1.

On the other hand, if t' [??] 1 over (G, x, f), then there exists an evaluation [[bar.y].sub.i],..., [[bar.y].sub.k] such that t' [not equal to] 1. Now, for the elements [h.sub.i] = s([[bar.y].sub.i]) we have t([h.sub.1],..., [h.sub.n]) [not equal to] 1, hence [??] 1 over (V, x, f).

Thus t [approximately equal to] 1 over (V, x, f) if and only if t' approximately equal to] 1 over (G, x, f). The reduction is polynomial in the length of t because the length of t' is the product of the length of t and the length of s, and s depends only on the group G.

Note that the converses of the statements of Lemma 9 are not true. With G = [A.sub.4] (the alternating group on 4 elements), V = G' and f being the commutator we have that the equivalence problem for (G, x, f) is coNP-complete and is in P for (V, x, f), and similarly, equation solvability for (G, x, f) is NP-complete and is in P for (V, x, f).

By the following lemma the equivalence problem can be reduced to the factor by the centralizer of a verbal subgroup, while the equation solvability problem can be reduced to the factor by a verbal subgroup.

Lemma 10 Let V be a verbal subgroup of G = (G, x). Let [H.sub.1] = ([H.sub.1], x) = G/[C.sub.G] (V) and let [H.sub.2] = ([H.sub.2], x) = G/V. Let f be a group term.

1. If the equivalence problem over ([H.sub.1], x, f) is coNP-complete, then the equivalence problem over (G, x, f) is coNP-complete.

2. If the equation solvability problem over ([H.sub.2], x, f) is NP-complete, then the equation solvability problem over (G, x, f) is NP-complete.

Proof: We prove (1). We give a polynomial reduction from the equivalence problem of ([H.sub.1], , f) to the equivalence problem of (G, x, f). For every term t([x.sub.1],..., [x.sub.n]) over ([H.sub.1], x, f) we present a term t' over (G, x, f) such that t [approximately equal to] 1 over ([H.sub.1], x, f) if and only if t' [approximately equal to] 1 over (G, x, f). As V is verbal, there exists a term s([x.sub.1],..., [x.sub.k]) over G such that s(G) = V. Let y = ([[bar.y].sub.1],..., [[bar.y].sub.k]). Let t ([x.sub.1],..., [x.sub.n]) be a term over ([H.sub.1], x, f) and let [bar.x] = ([x.sub.1],..., [x.sub.n]). Let the exponent of G be N. Consider the following term over (G, x,f):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Assume first that ([H.sub.1], x, f) [??] t [approximately equal to] 1. Then for every [bar.g] [member of] [G.sup.n] we have t([bar.g]) [member of] [C.sub.g](V). For arbitrary [bar.h] [member of] [G.sup.k] we have s([bar.h]) [member of] V. Thus [t ([bar.g]), s ([bar.h])] = 1, that is (G, x, f) = t' [approximately equal to] 1.

Assume now that (G, x, f) [??] t' [approximately equal to] 1. If [bar.y] runs through [G.sup.k], then s ([bar.y]) runs through V. Then for every [bar.g] [member of] [G.sup.n] we have t([bar.g]) [member of] [C.sub.G](V), i.e. ([H.sub.1],x,f) [??] t [approximately equal to] 1.

Thus t [approximately equal to] 1 over ([H.sub.1], x, f) if and only if t' [approximately equal to] 1 over (G, x, f). The reduction is polynomial in the length of t because [parallel]t'[parallel] [less than or equal to] N ([parallel]t[parallel] + [parallel]s^).

The proof of (2) is the same, except that instead of t' one should consider the following term:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Now, we prove Theorems 3 and 4. If G is not solvable, then the equivalence problem over (G, x) is coNP-complete Horvath et al. (2007), and the equation solvability problem over (G, x) is NP-complete Goldmann and Russell (2002). Thus for an arbitrary term f the equivalence problem over (G, x, f) is coNP-complete, and the equation solvability problem over (G, x, f) is NP-complete.

If G is nilpotent, then by Lemma 5 in Horvath (2011) there exists a positive integer d (depending only on G) such that for an arbitrary polynomial t ([x.sub.1],... ,[x.sub.n]) we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

That is we can obtain t (G, ..., G) by substituting only from [T.sub.d]. Now,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Hence we can obtain t (G,..., G) with O([n.sup.d]) many substitutions, thus in polynomial time of the length of t. Now, t [approximately equal to] 1 if and only if t (G,..., G) = { 1}. Moreover, t = 1 can be solved if and only if 1 [member of] t (G,..., G).

Now, we prove Theorem 3 for solvable, non-nilpotent groups by induction on the order of G.

Case 1: G' = (G', x) is non-nilpotent. As [absolute value of G'] < [absolute value of G], by the induction hypothesis there exists a term f such that the equivalence problem over (G', x, f) is coNP-complete. By (1) of Lemma 9 the equivalence problem over (G, x , f) is coNP-complete.

Case 2: G' is nilpotent, but G/[C.sub.G] (G') is non-nilpotent. Let H = G/[C.sub.G] (G'). As G' is nilpotent 1 = Z(G') [less than or equal to] [C.sub.G](G'), hence [absolute value of H] < [absolute value of G]. Since H = (H, x) is non-nilpotent, by the induction hypothesis there exists a term f such that the equivalence problem over (H, x, f) is coNP-complete. By (1) of Lemma 10 the equivalence problem over (G, x , f) is coNP-complete.

Case 3: G' and G/[C.sub.G] (G') are both nilpotent. Let A be the terminal element of the lower central series of G, i.e. A = [gamma](G). We prove that A and G/[C.sub.G] (A) are commutative groups. Now, G/[C.sub.G] (G') is nilpotent, and A is the terminal element of the lower central series, thus A [less than or equal to] [C.sub.G] (G'). Moreover, A < G' implies A [less than or equal to] [C.sub.G] (G') [intersection] G' = [C.sub.G] (G') = Z(G'), i.e. A is commutative. From A < [C.sub.G] (G') we have [C.sub.G] (A) [greater than or equal to] [C.sub.G] ([C.sub.G] (G')) [greater than or equal to] G'. Therefore G/[C.sub.G] (A) [less than or equal to] G/G', and G/[C.sub.G] (A) is commutative. Hence A and G/[C.sub.G] (A) are both commutative. Theorem 5 finishes the proof.

Finally, we prove Theorem 4 for solvable, non-nilpotent groups by induction on the order of G.

Case1: G' = (G', x) is non-nilpotent. As [absolute value of G'] < [absolute value of G], by the induction hypothesis there exists a term f such that the equation solvability problem over (G', x, f) is NP-complete. By (2) of Lemma 9 the equation solvability problem over (G, x, f) is NP-complete.

Case 2: G' is nilpotent, and G" [not equal to] 1. Since G is non-nilpotent and G' is nilpotent, we see from (Robinson, 1995, 5.2.10) that G/G" is non-nilpotent. Let H = G/G". As G" [not equal to] 1, we have [absolute value of H] < [absolute value of G]. Since H = (H, x) is non-nilpotent, by the induction hypothesis there exists a term f such that the equation solvability problem over (H, x, f) is NP-complete. By (2) of Lemma 10 the equation solvability problem over (G, x , f) is NP-complete.

Case 3: G' is nilpotent, G" = 1. Let A be the terminal element of the lower central series of G, i.e. A = [gamma](G). We prove that A and G/[C.sub.G] (A) are commutative groups. Now, G'' = 1 thus G' is commutative and A [less than or equal to] G' yields that A is commutative, as well. Moreover, from A [less than or equal to] G' we have [C.sub.G] (A) [greater than or equal to] [C.sub.G] (G') [greater than or equal to] [C.sub.G]> (G') = Z (G') = G'. Thus G/[C.sub.G] (A) [less than or equal to] G/G' and G/[C.sub.G] (A) is commutative. Hence A and G/[C.sub.G] (A) are both commutative. Theorem 5 finishes the proof.

4 Open questions

The term f in Theorems 3 and 4 varies from group to group. As it is mentioned in the Introduction, the commutator can significantly change the length of expressions. It is proved in Horvath and Szabo (2011) that the complexities of the equivalence and equation solvability problems change if we extend the alternating group [A.sub.4] by the commutator. One may wonder if f can be chosen as the commutator for every finite group.

Problem 1 For every finite group G = (G, x), determine the complexity of the equivalence and equation solvability problems for (G, x, [,]).

The smallest group for which it would be interesting to know how the commutator affects the complexity of the equivalence and equation solvability problems is [S.sub.3].

Problem 2 Determine the complexity of the equivalence and equation solvability problems for ([S.sub.3], x, [,]).

received 30th September 2010, revised 27th April 2011, accepted 28th April 2011.

Acknowledgements

This research was partially supported by the Hungarian National Foundation for Scientific Research grants K67870, N67867.

References

J. Almeida, M. V. Volkov, and S. V. Goldberg. Complexity of the identity checking problem for finite semigroups. Journal of Mathematical Sciences, 158(5):605-614, 2009.

R. Baer. Engelsche elemente noetherscher gruppen. Math. Ann., 133:256-270, 1957.

S. Burris and J. Lawrence. The equivalence problem for finite rings. J. ofSymb. Comp., 15:67-71, 1993.

S. Burris and J. Lawrence. Results on the equivalence problem for finite groups. Alg. Univ., 52(4): 495-500, 2004. (2005).

M. Goldmann and A. Russell. The complexity of solving equations over finite groups. Information and Computation, 178(253-262), 2002.

T. A. Gorazd and J. Krzaczkowski. The complexity of problems connected with two-element algebras. Reports on Mathematical Logic, 46:91-108, 2011.

G. Horvath. The complexity of the equivalence and equation solvability problems over nilpotent rings and groups. Algebra Universalis, 2011. to appear.

G. Horvith and Cs. Szabo. The complexity of checking identities over finite groups. Internat. J. Algebra Comput., 16(5):931-940, 2006.

G. Horvith and Cs. Szabo. Equivalence and equation solvability problems for the group A4. J. Pure Appl. Algebra, 2011. to appear.

G. Horvath, J. Lawrence, L. M6rai, and Cs. Szabo. The complexity of the equivalence problem for non-solvable groups. Bull. Lond. Math. Soc., 39(3):433-438, 2007.

H. Hunt and R. Stearns. The complexity for equivalence for commutative rings. Journal of Symbolic Computation, 10:411-436, 1990.

N. Jacobson. The radical and semi-simplicity for arbitrary rings. Amer. J. Math., 67:300-320, 1945.

R. M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85-103. Plenum, New York, 1972.

A. Kisielewicz. Complexity of semigroup identity checking. Int. J. of Alg. and Comp., 14(4):455-464, 2004.

O. Klima. Unification Modulo Associativity and Idempotency. PhD thesis, Masarik University, Brno, 2004.

O. Klima. Complexity issues of checking identities in finite monoids. Semigroup Forum, 79(3):435-444, 2009.

J. Lawrence and R. Willard. The complexity of solving polynomial equations over finite rings. manuscript, 1997.

S. Plescheva and V. Vortesi. Checking identities in 0-simple semigroups (in Russian). Journal of Ural State University, 43:72-102, 2006.

D. J. S. Robinson. A course in the theory of groups. Springer-Verlag, New York, Berlin, Heidelberg, 1995.

S. Seif and Cs. Szabo. Computational complexity of checking identites in 0-simple semigroups and matrix semigroups over finite fields. Semigroup Forum, 72(2):207-222, 2006.

Cs. Szabo and V. Vortesi. The equivalence problem over finite rings. Internat. J. Algebra Comput., 21(3): 449-457, 2011.

Gabor Horvath (1) ([dagger]) and Csaba Szabo (2) ([double dagger])

(1) Institute of Mathematics, University of Debrecen, Hungary

(2) Department of Algebra and Number Theory, Eotvos Lordnd University, Budapest, Hungary

([dagger]) Email: ghorvath@science.unideb.hu

([double dagger]) Email: csaba@cs.elte.hu
COPYRIGHT 2011 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Horvath, Gabor; Szabo, Csaba
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:4EXHU
Date:Dec 1, 2011
Words:6147
Previous Article:Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem.
Next Article:On the minimal distance of a polynomial code.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |