The Equational Theory of a Nontrivial Discriminator Variety is co-NP-hard

Stanley Burris

Abstract. Discriminator varieties play a central role in the classification of decidable varieties; and they arise naturally in the study of algebraic logics. There are also important connections with the reduction of theorem proving to equational logic. In this paper we show, for any nontrivial discriminator variety, that the problem of determining if an equation holds in the variety is co-NP-hard.

1. Background

A variety is a class of algebras closed under homomorphic images, subalgebras, and products; equivalently, it is a class of algebras defined by a set of equations. A variety V is generated by a class K of algebras, written V = V (K), if V is the smallest variety satisfying K ⊆ V. We say that a variety V is finitely generated if it can be generated by some finite set of finite algebras. For example the variety of distributive lattices is finitely generated – it is generated by any nontrivial class of distributive lattices. (A class of algebras is trivial if the algebras in it have only one element in them.)

We are interested in the equational theory of a class K of algebras, written Th_{eq}(K), which is just the set of equations true of every algebra in K. The problem of determining if s ≈ t ∈ Th_{eq}(K) is also called the equivalence problem for K. Since

Th_{eq}(K) = Th_{eq}(V (K))

holds, we simply say we are interested in the equational theories of varieties.

Proposition 1.1. If V is a finitely generated variety with a finite language then Th_{eq}(K) is co-NP.

Proof. Let K be a finite set of finite algebras generating V. Then V does not satisfy the equation s ≈ t iff s ≉ t is satisfiable in some member of K. The latter is clearly a problem in NP. □

For background on discriminator varieties the reader is referred to Burris [4] (1992) for a survey; and to Burris & Sankappanavar (1981), Chap. IV, for technical details.

Date: July 31, 2002.

This research was supported by a grant from NSERC.

A term t(x, y, z) is a discriminator term for an algebra A if the corollaryresponding function t^{A} satisfies, for a, b ∈ A,

t^{A}(a, b, c) = \{ \begin{matrix}a & if & a ≠ b \\ c & if & a = b. \end{matrix}

A variety V is a discriminator variety if there is a term t(x, y, z) which is a discriminator term for all the subdirectly irreducibles in V. The following are favorite examples of discriminator varieties.:

BA  Boolean algebras
BR  Boolean rings
RCDL  relatively complemented distributive lattices
P_{n}  n-valued Post algebras
x^{n} ≈ x-rings (for n > 1)
V (F_{1}, ⋯, F_{n}) a variety generated by finite fields
CA_{n}  cylindric algebras of dimension n
RA  relation algebras.

All but the last two of the above examples are finitely generated discriminator varieties, and hence their equational theories are co-NP. Looking at the above list, the complexity of the equational theories has been previously determined (and published in the literature) for BA, BR, and V (F_{1}, ⋯, F_{n}), where each F_{i} is a finite field. The co-NP-completeness of BA is essentially Cook’s pioneering work on SAT. The variety BR and, more generally, V (F) were proved co-NP-complete in Bloniarz, Hunt, & Rosenkrantz [2] (1984) (along with the variety generated by the ring Z_{k} of integers modulo k, for k > 1). The results of Hunt & Stearns [7] (1990) on nonnilpotent finite commutative rings covers the case of a variety generated by finitely many finite fields F_{i} (just consider the ring Π_{i=1}^{n}F_{i}).

These, along with the “if-then-else” discriminator varieties studied in Bloom & Tindell [1] (1983) and Mekler & Nelson [9] (1987), are the basic examples studied in the literature.

Our technique for showing co-NP-hardness is to efficiently reduce distributive lattice equations to equations in the target discriminator variety. For this purpose we introduce some notation.

1.1. The (⋁, ⋀) - classes of lattice terms. Because of the associative law it is common practice to drop numerous parentheses when writing out a lattice term t, for example,

x_{1} ∨ (((x_{2} ∧ x_{3}) ∧ x_{4}) ∨ x_{5})

would be simply written as

x_{1} ∨ (x_{2} ∧ x_{3} ∧ x_{4}) ∨ x_{5}.

Such expressions will be called generalized lattice terms. The translation of a lattice term into its generalized form will be denoted by t^{⋆}. This translation leads to a classification of the t [or t^{⋆}]; in our example above we have a ⋁ ⋀ [generalized] term. Likewise one has ⋁ ⋀ ⋁ [generalized] terms, etc. The set of all lattice terms having the generalized form ⋁ ⋀ ⋁ is called the ⋁ ⋀ ⋁ - class; this is an example of a (⋁, ⋀) - class.

One can refine this classification by adding ⋁_{n}, ⋁_{≤n}, etc., to indicate exactly n, or ≤ n, arguments in the generalized operations. The class ⋀ ⋁_{3} is important because of the use made of 3-SAT.

For computer implementations we could express the generalized form t^{⋆} of a term t by a list; in our example above we could use

( ⋁ x_{1} (⋀ x_{2} x_{3} x_{4}) x_{5}).

The translation of a lattice term, say in prefix form, to such a list is clearly a polynomial time procedure.

The following key result for this paper is extracted from Theorem 3.1 of [2].

Theorem 1.2 (Bloniarz, Hunt III, & Rosenkrantz, 1984). The set of lattice equations of the form ⋀ ⋁_{2} ≈ ⋁ ⋀ ⋁_{≤2} that are true of distributive lattices is co-NP-hard.

2. Efficient encoding of lattice terms

Let us consider the translation of a lattice term t into any language L of algebras by using L-terms r_{1}(x, y), respectively r_{2}(x, y), to replace occurrences of ∨, respectively ∧. We use T_{r_{1}r_{2}}(t) to denote this translation.

If either r_{1} or r_{2} has a repeated variable then such a translation procedure is not polynomial time bounded as the size of the translated terms can grow too fast. [Suppose r_{1}(x, y) has a repeated variable. Then, for t = x_{1} ∨ (x_{2} ∨ (⋯ (x_{n−1} ∨ x_{n}) ⋯), the term T_{r_{1}r_{2}}(t) has size at least 2^{n}.] This was the problem faced, and solved, by Bloniarz, Hunt III, & Rosenkrantz [2] when trying to encode BA equations of the form ⋁ ⋀_{3} ±var ≈ 1 into the language of rings. (Hunt III & Stearns avoided this problem by translating BA equations of the form ⋀ ⋁_{3} ±var ≈ 0.) We will expand on their technique to get around the explosive encoding so as to give an efficient procedure for encoding lattice terms. Given a lattice term t it will yield T_{r_{1}r_{2}}(t′) for some lattice term t′ which is equivalent (by associativity alone) to t. Finding the term T_{r_{1}r_{2}}(t′) will be a polynomial time procedure when restricted to lattice terms whose height is bounded by some constant — this basically generalizes the process used by Bloniarz, Hunt III, & Rosenkrantz [2] (1984), p. 895, on terms in ⋁ ⋀_{3}.

2.1. The transformations τ_{r_{i}}. Given L-terms r_{1}(x, y) and r_{2}(x, y) define the transformations τ_{r_{i}} from finite sequences s of lattice terms to L-terms by letting τ_{r_{i}}(s) be the single term in the list output by the following program, where ℓ(s) is the length of a sequence s:

Let t = s

LOOP until ℓ(t) = 1 Let ℓ = ℓ(t)

let t = \{ \begin{matrix}(r_{i}(t_{1}, t_{2}), ⋯, r_{i}(t_{ℓ−1}, t_{ℓ})) & for & ℓ even \\ (r_{i}(t_{1}, t_{2}), ⋯, r_{i}(t_{ℓ−2}, t_{ℓ−1}), t_{ℓ}) & for & ℓ odd. \end{matrix}

ENDLOOP Let ||t|| = ∑_{i=1}^{ℓ(t)} |t_{i}|. Note that ||t|| is increasing with every pass through the

loop, and the number of passes is bounded by log_{2}ℓ(s) + 1. From the easily derived inequality

|r_{i}(t_{j}, t_{j+1})| ≤ |r_{i}(x, y)|(|t_{j}| + |t_{j+1}|)

we see that in a single pass the size of ||t|| increases at most by a factor of 2|r_{i}(x, y)|. Thus, with C_{i} = 2|r_{i}(x, y)|, we can conclude that

|τ_{r_{i}}(s)| ≤ C_{i}^{log_{2}ℓ(s)+1} · ||s||.  (2.1)

So the procedure to find τ_{r_{i}}(s) is polynomial time.

2.2. The translation τ_{r_{1}r_{2}}. We now use these procedures to define a translation τ_{r_{1}r_{2}} from generalized lattice terms t^{⋆} into L-terms, using □_{1} for ∨, □_{2} for ∧:

τ_{r_{1}r_{2}}(x) = x for x a variable
τ_{r_{1}r_{2}}(t_{1}^{⋆} □_{i} ⋯ □_{i} t_{n}^{⋆}) = τ_{r_{i}}(τ_{r_{1}r_{2}}(t_{1}^{⋆}) □_{i} ⋯ □_{i} τ_{r_{1}r_{2}}(t_{n}^{⋆}))

Observe that if we start with a lattice term t and use r_{1}(x, y) = x∨y and r_{2}(x, y) = x∧y then t′ = τ_{∨∧}(t^{⋆}) is a lattice term which is equivalent (using only the associative laws) to t. And then for any L-terms r_{1}(x, y) and r_{2}(x, y) we have τ_{r_{1}r_{2}}(t^{⋆}) = T_{r_{1}r_{2}}(t′).

Now fix L-terms r_{1}(x, y) and r_{2}(x, y) and choose C_{i} as in (2.1); and let C = max(C_{1}^{2}, C_{2}^{2}).

To measure the complexity of calculating τ_{r_{1}r_{2}}(t^{⋆}) we introduce the height h(t) of a lattice term t, defined to be the number of ⋁’s and ⋀’s in the description of the (⋁, ⋀) - class to which it belongs. Thus in our example above we have a term of height 2.

Lemma 2.1. For any lattice term t we have

|τ_{r_{1}r_{2}}(t^{⋆})| ≤ |t|^{h(t)·log_{2}C+1}.  (2.2)

Proof. We proceed by induction on h(t). For h(t) = 0 we have t is a variable, thus τ_{r_{1}r_{2}}(t^{⋆}) = t, so (2.2) holds.

For h(t) > 1 we assume (2.2) holds for lattice terms of smaller height. Then let

t^{⋆} = t_{1}^{⋆} □_{i} ⋯ □_{i} t_{n}^{⋆}

where h(t_{j}) < h(t) for 1 ≤ j ≤ n. By definition

τ_{r_{1}r_{2}}(t_{1}^{⋆} □_{i} ⋯ □_{i} t_{n}^{⋆}) = τ_{r_{i}}(τ_{r_{1}r_{2}}(t_{1}^{⋆}) □_{i} ⋯ □_{i} τ_{r_{1}r_{2}}(t_{n}^{⋆}))

so

|τ_{r_{1}r_{2}}(t^{⋆})| ≤ C_{i}^{log_{2}n+1} ∑_{j=1}^{n} |τ_{r_{1}r_{2}}(t_{j}^{⋆})|  by (2.1)

≤ C_{i}^{2log_{2}|t|} ∑_{j=1}^{n} |t_{j}|^{h(t_{j})·log_{2}C+1}  induction hypothesis

≤ C^{log_{2}|t|} ∑_{j=1}^{n} |t_{j}|^{(h(t)−1)·log_{2}C+1}

≤ C^{log_{2}|t|} (∑_{j=1}^{n} |t_{j}|)^{(h(t)−1)·log_{2}C+1}
≤ |t|^{log_{2}C}|t|^{(h(t)−1)·log_{2}C+1}
≤ |t|^{h(t)·log_{2}C+1}
□

Corollary 2.2. For lattice terms t with height bounded by some constant, the translation from t to τ_{r_{1}r_{2}}(t^{⋆}) can be carried out in polynomial time.

2.3. Application to the complexity of Th_{eq}(K). Now we are ready to give our general setup. With x⃗ = (x_{1}, ⋯, x_{n}) we use fx⃗ for (fx_{1}, ⋯, fx_{n}).

Proposition 2.3. Suppose K is a class of L-algebras for which there are L-terms f(x), r_{1}(x, y), r_{2}(x, y) such that for any lattice equation s(x⃗) ≈ t(x⃗)

DL ⊧ s(x⃗) ≈ t(x⃗)  iff  K ⊧ T_{r_{1}r_{2}}(s)(fx⃗) ≈ T_{r_{1}r_{2}}(t)(fx⃗).

Then Th_{eq}(K) is co-NP-hard. It is co-NP-complete if K is a finite collection of finite algebras.

Proof. Let s′ = τ_{r_{1}r_{2}}(s^{⋆}), t′ = τ_{r_{1}r_{2}}(t^{⋆}). As DL satisfies s ≈ s′ and t ≈ t′ we have

DL ⊧ s(x⃗) ≈ t(x⃗)  iff  K ⊧ T_{r_{1}r_{2}}(s′)(fx⃗) ≈ T_{r_{1}r_{2}}(t′)(fx⃗).

As the set of s ≈ t in Th_{eq}(DL) of the form ⋀ ⋁ ≈ ⋁ ⋀ ⋁ is co-NP-hard by Theorem 1.2, and since the translation

from  s(x⃗) ≈ t(x⃗)  to  T_{r_{1}r_{2}}(s′)(fx⃗) ≈ T_{r_{1}r_{2}}(t′)(fx⃗)

can, for lattice terms of height ≤ 3, be carried out in polynomial time by Corollary 2.2, it follows that Th_{eq}(K) is co-NP-hard. If K is finite then Th_{eq}(K) is clearly co-NP. □

3. Using principal congruences for the encoding.

Before delving into the proof of the main result we need to collect some useful definitions and facts. From now on we assume we are working with a fixed nontrivial discriminator variety V, and with a term t(x, y, z) which is a discriminator term on the subdirectly irreducible algebras in V. Define the term s(x, y, u, v) by

s(x, y, u, v) = t(t(x, y, u), t(x, y, v), v).

Given any algebra A we know (from Birkhoff’s work in the 1930’s) that the congruences of A form a lattice Con(A). Our strategy is to make heavy use of the nice behavior of congruence lattices in discriminator varieties. Con(V) denotes the class of lattices CON(A), for A ∈ V. Let DL denote the variety of distributive lattices.

Lemma 3.1. Con(V) ⊆ DL.

Proof. See Burris & Sankappanavar [3] (1981), p. 165. □

For A ∈ V and a, b ∈ A let Θ(a, b) be the principal congruence of A generated by ⟨a, b⟩.

Lemma 3.2. For A ∈ V and a, b, c, d ∈ A (a) Θ(a, b) ∨ Θ(c, d) = Θ(t(a, b, c), t(b, a, d))

(b) Θ(a, b) ∧ Θ(c, d) = Θ(s(a, b, c, d), c)

(c) Θ(a, b) = Θ(c, d) iff t(t(a, b, c)t(a, b, d), t(c, d, a)) = t(t(a, b, d), t(a, b, c)t(c, d, b)).

Proof. The first two are on p. 166 of Burris & Sankappanavar [3] (1981). The third can easily be derived from the other facts on that page. □

Lemma 3.3. Let ε(x_{1}, ⋯, x_{n}) be a lattice equation. Then

DL ⊧ ε(x_{1}, ⋯, x_{n})  iff  Con(V) ⊧ ε(Θ(x_{1}, y_{1}), ⋯, Θ(x_{n}, y_{n})).

Proof. The direction (⟹) is obvious from Lemma 3.2. For (⟸) let A be a nontrivial simple algebra in V. Then for a, b ∈ A

Θ(a, b) = \{ \begin{matrix}Δ & if & a ≠ b \\ ∇ & if & a = b, \end{matrix}

where Δ = {⟨a, a⟩ : a ∈ A}, and ∇ = A × A. By letting x_{i}, y_{i} range over A we see (since |A| > 1) that the Θ(x_{i}, y_{i}) can independently take on the values Δ, ∇. Thus ε(x_{1}, ⋯, x_{n}) holds on the two-element distributive lattice ⟨{Δ, ∇}, ∨, ∧⟩; so it must hold on all distributive lattices. □

Now we are ready to prove the main result.

Theorem 3.4. Let V be a nontrivial discriminator variety. Then the equational theory of V is co-NP-hard. If V is also finitely generated then Th_{eq}(V) is co-NP-complete.

Proof. All we need is an efficient way to convert ε(Θ(x_{1}, y_{1}), ⋯, Θ(x_{n}, y_{n})) into an equation ε^{⋆}(x_{1}, y_{1}, ⋯, x_{n}, y_{n}) in the language of V such that

Con(V) ⊧ ε(Θ(x_{1}, y_{1}), ⋯, Θ(x_{n}, y_{n}))  iff  V ⊧ ε^{⋆}(x_{1}, y_{1}, ⋯, x_{n}, y_{n}).

(3.1)

For then we can use Lemma 3.1. The key idea is to use Lemma 3.2—the first two items of this lemma allow one to eliminate the ∨’s and ∧’s; and then the last item gives an equation such that (3.1) holds. Unfortunately a direct application of Lemma 3.2 to ε(Θ(x_{1}, y_{1}), ⋯, Θ(x_{n}, y_{n})) will sometimes give an exponentially larger ε^{⋆}. To avoid this problem we invoke the results from section 2 to transform ε into an equivalent ε′ (using just the associative laws) such that applying Lemma 3.2 to ε′ leads to a “small” equation ε^{⋆} satisfying (3.1). Thus we have, using Lemma 3.1,

DL ⊧ ε(x_{1}, ⋯, x_{n}) iff V ⊧ ε^{⋆}(x_{1}, y_{1}, ⋯, x_{n}, y_{n}).

Consequently Th_{eq}(V) is co-NP-hard, by Lemma 3.3; and by Proposition 1.1, if V is finitely generated then Th_{eq}(V) is co-NP-complete. □

References

[1] Stephen L. Bloom and Ralph Tindell, Varieties of “if-then-else”. Siam J. Comput. 12 (1983), 677–707.

[2] P.A. Bloniarz, H.B. Hunt III, D.J. Rosenkrantz, Algebraic structures with hard equivalence and minimization problems. J. Assoc. for Computing Machinery, 31 (1984), 879–904.

[3] Stanley Burris and H.P. Sankappanavar, A Course in Universal Algebra. Springer Verlag, 1981.

[4] Stanley Burris, Discriminator varieties and symbolic computation. J. Symbolic Computation 13 (1992), 175–207.

[5] I.N. Herstein, Noncommutative Rings. Carus Math. Monographs, Math. Assoc. of America, 1968.

[6] H.B. Hunt III, D.J. Rosenkrantz,& P.A. Bloniarz, On the computational complexity of algebra on lattices. Siam J. Comput. 16 (1987), 129–148.

[7] H.B. Hunt III & R.E. Stearns, The complexity of equivalence for commutative rings. J. Symbolic Computing 10 (1990), 411–436.

[8] O.G. Kharlampovich and M.V. Sapir, Algorithmic problems in varieties.

Internat. J. Algebra Comput. 5 (1995), 379–602.

[9] Alan H. Mekler and Evelyn M. Nelson, Equational bases for if-then-else logic. Siam J. Comput. 16 (1987), 465–485.

Dept. of Pure Mathematics, University of Waterloo, Waterloo, Ont., Canada N2L 3G1

  E-mail address: snburris@thoralf.uwaterloo.ca