Computational complexity of some problems involving congruences on algebras.
We prove that several problems concerning congruences on algebras are complete for nondeterministic log-space. These problems are: determining the congruence on a given algebra generated by a set of pairs, and determining whether a given algebra is simple or subdirectly irreducible. We also consider the problem of determining the smallest fully invariant congruence on a given algebra containing a given set of pairs. We prove that this problem is complete for nondeterministic polynomial time.
A and a lies in

the subuniverse of A generated by
It is easy to nd a reduction of Gen-Con to Gen-SubAlg, see for example,
[3, Theorem 5.5]. Thus Gen-Con can be no harder than Gen-SubAlg.
However, in [14] Jones and Laaser proved that Gen-SubAlg is complete
for P (the class of problems solvable in polynomial time). It is known that
NL is contained in the class of problems solvable in polynomial time, and
it is generally believed that the inclusion is proper. Thus Gen-SubAlg is
apparently strictly harder than Gen-Con.
Since it lies in NL, there is an algorithm for Gen-Con that runs in
polynomial time. Our Algorithm 1 is, of course, nondeterministic. But
even if it were converted to a deterministic algorithm in the natural way
(i.e., by an exhaustive search for a successful computation path), it would
not be particularly ecient, running in time proportional to the square,
or perhaps even the cube of s, the size of the input. This is because the
algorithm repeatedly recomputes numerous quantities, rather than saving
them (since the space required to save the information exceeds O(log s)
bits). By contrast, in a recent note [7], R. Freese exhibited an algorithm for
Gen-Con that runs in linear time. However, Freese's algorithm uses linear,
rather than logarithmic, space. In the 1980s, Demel, Demlova and Koubek
[4, 5] presented linear-time algorithms for many of the problems discussed
in this paper.
1. Background Material
We provide here only the barest summary of the notions we need from
universal algebra and complexity theory. For more details on universal al-
gebra, the reader should consult any of [3, 9, 19], and for computational
complexity, [11, 20, 22]. Also, the rst two sections of our paper [2] contain
a more extensive discussion of both of these topics.
For a nonnegative integer n, an n-ary operation on a set A is a function
A. The integer n is called the rank of f. An algebra is a pair
Fi, in which A is a nonempty set, and F is a set of operations on
A. The set A is called the universe and F the set of basic operations of the
algebra A. If F is nite, the algebra is said to be of nite similarity type.
A subuniverse of A is a subset closed under the basic operations.
Denition 1.1. Let Fi be an algebra. A congruence on A is a set
A A such that
is an equivalence relation on A, and

Here, the rank of f is n.
The set of congruences on A is denoted Con(A). The smallest element
of this set is the identity relation while the largest
is the relation A2. It is easy to see that Con(A) is closed under arbitrary
nonempty intersections. Given a set A A we dene
called the congruence on A generated by .
A nontrivial algebra A is called simple if while A is
called subdirectly irreducible if there is a A such that for all2 Con(A) fAg, . The congruence is called the monolith of A.
The formal denitions of complexity theory are usually given in terms of
languages, i.e., sets of nite strings over some xed alphabet. Associated
with each language L is a decision problem: Given a string x, decide whether
L. The amount of time or space required by a Turing machine to perform
this computation generally depends on the length of the input string x.
The language L is said to be computable in polynomial time if there is
a polynomial p such that some deterministic Turing machine can decide

whether an input string x of length s lies in L in time O p(s) . The set of
all languages computable in polynomial time is denoted P.
The set NL consists of those languages computable by a nondeterministic
Turing machine whose space requirements are in O(log s), for an input
of length s. We say that such a problem is computable in nondeterministic
log-space. Similarly, NP denotes the set of languages computable in
nondeterministic polynomial time.
Of course in practice, we prefer to couch our discussion in terms of \real"
problems, rather than languages. But we always tacitly assume that there is
some reasonable encoding of the instances of the problem into nite strings.
In this way, we can identify our mathematical problems with formal lan-
guages, and we describe our problems as certain subsets of the set of all
appropriate instances.
Given two problems A and B, we say that A is log-space reducible to B
log B) if there is a function f, computable in (deterministic) log-space,
such that for every instance x of A, x 2 A () f(x) 2 B. B is said to be
hard for NL if every member of NL is log-space reducible to B, and B is
complete for NL if it is both hard for NL and a member of NL. It is not
hard to see that 'log' is reexive and transitive. Thus if B is known to be
NL-complete and if B log A 2 NL, then A is NL-complete as well.
It is not hard to show that NL P NP. It is generally believed,
although still unproved, that each of these inclusions is proper. It follows
from this belief that a proof that a problem B is complete for one of these
classes is strong evidence that B does not belong to any of the preceding
classes in this list of inclusions.
We make the following assumptions regarding the format of an input
instance to the problems Gen-Con, Simp and SI. All algebras are nite and
of nite similarity type. The underlying set of an algebra can be assumed
to be f0; positive integer n, and, in fact, this set can
be represented in the input by its cardinality. This requires only log n bits
of storage. Each operation of an algebra can be represented as a table of
values. Thus, a k-ary operation will be represented as a k-dimensional array,
with both the indices and entries coming from n1g. An array such
as this occupies nk log n bits in the input stream.
Fi be an algebra of cardinality n. Suppose that
the maximum rank of any member of F is r. Then, as an input instance
to either Simp or SI, the size of A is at least max(nr; nq). Similarly, let
s denote the size of a typical instance, of Gen-Con. This is
bounded below by max(nr; jj ; nq). We can certainly conclude that
log s max(r log n; log q):
2. Membership in NL
In order to prove that Gen-Con lies in NL, we need a slight variation
on the classical theorem, due to Maltsev [18], describing the congruence on
an algebra A generated by a set of pairs. The only dierence between our
formulation and that found in most texts is that we replace the monoid of
all unary polynomial operations on A with a smaller and more manageable
subset that we now describe. The proofs of Lemma 2.1 and Theorem 2.2
are identical to those of Theorems 4.18 and 4.19 in [19]. A treatment very
similar to ours can be found in Section 2.1.2 of [24].
Let A be a set and f an n-ary operation on A, for some n 1. We dene

an
Thus, f(A) is the set of all unary operations on A obtained by substituting
elements of A for all but one of the variables in f. The members of f(A) are
called elementary translations. We write C(A) for the set of unary constant
operations on A. Finally, if F is any set of operations on A, we let

Lemma 2.1. Let A be a set and let F be a set of operations on A. Then
Algorithm
(1) z a, n jAj
(3) Choose z0 2 A
Choose (u; v) 2
do
Choose
od
Reject
od
Reject
For a set S of unary operations on A, let S denote the submonoid of the
monoid of all self-maps of A generated by S. In particular, the identity map
is an element of S.
Theorem 2.2. Let Fi be a nite algebra, A A and a; b 2 A.
only if there are elements
pairs
such that
(2)
Notice that in the above theorem, we can assume that m < jAj. For
if not, then there are indices j < k such that In that case, the
sequence (along with the associated sequence of
(ci; di) and fi) serve as witnesses to (a; b) 2 CgA().
It is a simple matter to turn the characterization in Theorem 2.2 into a
procedure for computing Gen-Con.
Theorem 2.3. Gen-Con 2 NL.
Proof. Consider the nondeterministic algorithm labeled Algorithm 1. Essentially
this procedure takes a guess at the sequences z0;
Theorem 2.2. If it nds such sequences, the
algorithm accepts the input In each trip through the main loop
(starting at statement 2), z contains the value of zi. We nondeterministically
choose values z0 to be zi+1 and u; v to be ci; di. In steps 5{9, we choose an
operation f 2 F(A) and test whether fz; f(di)g. If this equality
holds, we set (at step 12) zi+1 to be the value of z0 and continue. If the
equality fails, we reject the instance.
The computation of the operation f is accomplished by nondeterministically
choosing a series of operations g 2 F(A) whose composite is to be f. We
don't keep track of all of these g's. Rather, we follow the images of ci and
di under these maps by recording them in the variables u and v. The length
of the composition needed to obtain f can be bounded by n2, since that is
how many pairs (u; v) are possible. (And there is no need to encounter a
more than once.)
It is also not necessary to construct the entire set F(A) in line 7. The
set is part of the input. For
be the constant operation with value i. To choose g, pick integers k and
ar
of A. The data hk; is sucient to determine the operation
The total auxiliary memory required by Algorithm 1 is the space for
storing the variables: z; z0; ar. Each of these holds an
integer in the range [0; n), hence requires only log n bits of storage, except
for k and ' which require log(q+n) and log r bits respectively. Thus the total
space requirement is on the order of (r+7) log n+log(q+n)+log r 2 O(log s),
where s is the size of the instance, by the inequality (1).
Theorem 2.3 can also be obtained from Immerman's theorem [12]. Immerman
showed that every language denable in FO(TC) (rst-order logic
with a transitive closure operator) lies in NL. It follows from Theorem 2.2
that Gen-Con can be so dened. Similar remarks apply to the following
theorem.
Theorem 2.4. Both Simp and SI lie in NL.
Proof. Observe that a nontrivial algebra A is simple if and only if
For each a; b; c; d, the truth of (a; b) 2 CgA(c; d) can be determined with a
single call to Gen-Con. The computation required to verify formula (3) can
be accomplished with four nested loops. It is important to observe that the
space required for the call to Gen-Con can be reused on each trip through
the loop. Thus, in addition to the space required by one call to Gen-Con,
we only need to allocate space for the four loop counters, which run from 0
to jAj 1. Thus Simp 2 NL.
Similarly, A is subdirectly irreducible if and only if
Using an argument similar to that used for simplicity, we see that SI 2 NL.
We conclude this section with a discussion of a problem rst considered
in Belohlavek and Chajda [1]. Let us dene

A an algebra and C a congruence class

of some congruence on A :
If is a congruence of an algebra A, then a congruence class of is a set
of the form for some xed element a of A.
Belohlavek and Chajda show that when restricted to those algebras that
generate a congruence-regular variety, the problem Cong-Class lies in P.
However, using the techniques we have developed in this section, we are able
to show that not only can the congruence-regularity assumption be dropped,
but Cong-Class actually lies in NL, a (presumably proper) subclass of P.
Theorem 2.5. Cong-Class 2 NL.
Proof. Let A be an algebra, and C A. Since the empty set is never a
congruence class, we assume that C is nonempty.
It is easy to see that C is a class of some congruence if and only if C is a
class of the congruence . Fix an element c 2 C. By the denition of ,
we clearly have C c= , thus we need only check the reverse inclusion. In
other words, we wish to check the condition
This condition can be checked with a simple loop. Strictly speaking, we can
not call Gen-Con as a subroutine, since that would require enough space
to hold the structure hA; C2; x; ci. Instead, the code from Algorithm 1 must
be inserted directly into the loop with references to replaced by C. Thus
Cong-Class lies in NL.
Unlike our primary problems, Gen-Con, SI and Simp, we have been
unable to determine whether Cong-Class is complete for NL. We leave
that as an open problem.
Problem. Is Cong-Class complete for NL?
3. NL-Hardness of the problems
We now turn to the problem of determining a lower bound for each of
these problems. Specically, we wish to show that each of the three problems
discussed in Theorems 2.3 and 2.4 is NL-hard. For this we will use some
facts from the complexity theory of nite graphs.
A directed graph (digraph) is a structure hG; "i, in which G is a nonempty,
nite set (the vertices) and " G G (the edges).
hG; "i be a digraph and a; b 2 G. A path from a to b of length n
is a sequence of vertices such that for every 0 i < n,
". For every vertex a, we agree that there is a path from a to a
(of length 0). We dene
there is a path from a to b
One of the best-known problems in complexity theory is the Graph Accessibility

In other words, GAP is the problem of determining whether there is a path
from a to b in a given digraph. This problem was shown to be complete
for NL in [13], although the result is also implicit in [21]. It is used as the
motivating problem for nondeterministic log-space in [20], where it is called
REACHABILITY.
The digraph G is called strongly connected if for every a 2 G, G.
In other words, for every a and b, there is a directed path from a to b.
The vertex b will be called an attractor if, for every vertex a, b 2 R(a).
Associated with these notions, we introduce two more problems.
strongly connected g
has an attractor
Str-Con was proved to be NL-complete by Laaser, see [13]. As far as we
know, the problem Attract is new.
Theorem 3.1. Each of the problems GAP, Str-Con and Attract is
complete for NL.
Proof. We mentioned above that both GAP and Str-Con are complete for
NL. Let G be a digraph. Observe that
In a manner similar to that used for SI in the proof of Theorem 2.4, an
algorithm for Attract (and also for Str-Con) can be based on two nested
loops, with a call to GAP inside the innermost loop. The space used for
the GAP computation can be reused. Thus Attract lies in NL.
To show that Attract is NL-hard, we shall give a log-space reduction of
GAP to Attract. Let hG; a; bi be an instance of GAP, where
c)g. Let
We claim that hG; a; bi 2 GAP if and only if H 2 Attract,
with c as the attractor.
To see this, suppose rst that there is a path p from a to b in G. Then
for any vertex v of G, the sequence v; p; c is a path in H from v to c. Thus
c is an attractor. Conversely, if c is an attractor in H, then there is a path
(in H) from a to c. But such a path must include b, and (since there is no
exit from c) only the last vertex in the path is equal to c. Thus, there is a
path in G from a to b, so that hG; a; bi 2 GAP.
This reduction is clearly computable in log-space, since the only auxiliary
storage that is needed is for several counters. Thus Attract is NL-
complete.
gw

Figure

1. Part of an algebra A(G)
The reader has surely noticed the structural similarity between the conditions
in (5) and those in equivalences (3) and (4):
We shall now exhibit reductions between the graph problems of Theorem 3.1
and the algebra problems discussed in Theorem 2.4. For this we use the
following construction.
hG; "i be a digraph. Fix an element ? 2= G and let G[f?g.
Dene a new graph (Thus ? is an isolated point of G?.)
For (the closed neighborhood

of v), and let choose a function
in such a way that for all
In other words, for each edge from v to w there should be some i with
Note that for all i we have Also, for each v 2 G we
dene the operation gv on G? by
w otherwise.
Finally, we dene an algebra
The construction of A(G) is illustrated schematically in Figure 1.
Let us make two observations about the algebra A(G). First, for any
element a of G, the subuniverse generated by a is R(a)[f?g. Second, A(G)
is a unary algebra, that is, each of its basic operations is of rank 1. A useful
fact about unary algebras is the following lemma. The proof is an easy
verication.
Lemma 3.2. Let B be a unary algebra and S a subuniverse of B. Then the
binary relation is a congruence on B.
Note that the congruence S has exactly one nontrivial congruence class,
namely S itself. For the next two lemmas, we omit the superscript 'A(G)'
in the notation Cg(x; y).
Lemma 3.3. (1) Let a and b be vertices of G. Then (b; ?) 2 Cg(a; ?) if
and only if b 2 R(a).
(2) If c and d are distinct elements of G?, then Cg(c; ?) Cg(c; d).
Proof. Let be the subalgebra of A(G) generated by a.
it follows from Lemma 3.2 that Cg(a; ?) S. Thus, if
R(a).Conversely, if b 2 R(a), then there is a sequence of indices
such that xed by each fi, we obtain
For the second claim, if then the inclusion is trivial. So suppose
working modulo Cg(c; d) we have
is the smallest congruence identifying c with ?, we
get Cg(c; ?) Cg(c; d).
The relationship between the algebraic problems and the graph problems
is given in the following lemma.
Lemma 3.4. For any digraph G and a; b 2 G we have

hG;
Proof. The rst equivalence follows immediately from Lemma 3.3(1). Suppose
that G is strongly connected. To show A(G) simple, pick a pair c; d
of distinct elements from G?. We wish to show that Cg(c; d) is the universal
congruence. Without loss of generality, assume that c = ?. ByLemma 3.3(2), we have (c; ?) 2 Cg(c; d). By assumption
Lemma 3.3(1), the congruence class of c modulo Cg(c; ?) contains all of G?.
Thus Cg(c; ?), hence also Cg(c; d) is universal.
Conversely, suppose that A(G) is simple. Pick vertices a; b in G. Since
Cg(a; ?) is the universal congruence, we apply Lemma 3.3(1) again to obtain
Now we address the third equivalence. Suppose that b is an attractor of
G. We wish to show that Cg(b; ?) is the smallest nontrivial congruence (the
monolith) of A(G). Choose any pair c; d of distinct elements. Assume that
using Lemma 3.3, Cg(b; ?) Cg(c; ?) Cg(c; d).
For the converse, suppose that Cg(c; d) is the monolith of A(G), with
not the identity congruence, hence by the minimality of Cg(c; d), we get
for any a 2 G, Cg(c; ?) Cg(a; ?), hence by
Lemma 3.3(1), c 2 R(a). In other words, c is an attractor of G.
Finally, we can combine Lemma 3.4 and Theorem 3.1 to obtain our main
theorem.
Theorem 3.5. Each of the problems Gen-Con, Simp and SI is complete
for NL.
Remarks:
(1) From Lemma 3.4 we see that Gen-Con remains complete for NL
if we restrict to instances hA; ; a; bi in which A is a unary algebra
and
(2) It is natural to wonder about the complexity of recognizing congruences
on an algebra. In other words, given an algebra A and a binary
relation on A, determine whether is a congruence on A. It is not
hard to see that this can be done in (deterministic) log-space.
First, one can verify that is an equivalence relation using three
nested loops, each running through the elements of A. For example,
if a and b are two of the loop counters, then we can test the symmetry
of by verifying that whenever (a; b) is in , so is (b; a).
To test the second condition of Denition 1.1, use two sets of variables
ar and denotes the maximum rank of
any of the basic operations.) For each basic operation f, have each of
traverse the entire set Ar. Whenever we

have (ai; bi) 2 for all i k, verify that
. This requires 2r counters, each using log n bits. Note that an input
instance to this problem is almost identical to that of Gen-Con,
so we conclude from inequality (1) that our space requirements are
bounded by the logarithm of the size of the input.
(3) In the construction of A(G), the sequence hgviv2G of unary operations
can be replaced with a single binary operation given by
y otherwise.
This does not result in any space-saving when all operations are
given via tables, but might be very ecient if the operations are
allowed to be presented by other means, such as Boolean circuits.
(4) GAP is a problem for directed graphs. There is an analogous prob-
lem, called UGAP, for undirected graphs. It follows at once that
However, it is an open question whether UGAP is
complete for NL. The complexity class SL (symmetric log-space) is
dened in such a way that UGAP is complete for SL. See Lewis and
Papadimitriou[16] for details. The completeness of UGAP for NL
is equivalent to the assertion that
A set A can be viewed as an algebra in which the set of basic
operations is empty. In that case, for any subset of A2, CgA()
is nothing but the smallest equivalence relation on A containing .
Now it is easy to see that (a; b) 2 CgA() if and only if a and b lie in
the same connected component of the undirected graph hA; i, where
g. In other words, UGAP coincides with
the special case of Gen-Con in which the \algebra" is constrained
to have no basic operations. In our experience, this special case is
of lesser complexity than is the general case. This suggests that one
ought to try to prove that Gen-Con 2= SL, thereby settling the
question of whether SL and NL are distinct.
Recall the problem Cong-Class mentioned at the end of Section
2. We proved in Theorem 2.5 that Cong-Class lies in NL.
Since we have been unable to prove that this problem is complete
for NL, we are led to wonder whether Cong-Class might lie in an
interesting proper subclass. SL seems to be a natural candidate. As
a companion to Problem 2, we ask
Does Cong-Class lie in SL?
4. Fully invariant congruences
An endomorphism of an algebra Fi is a homomorphism from A
to itself, in other words, a function A such that for all f 2 F and

. The collection of
all endomorphisms of A is denoted End(A).
A congruence on A is called fully invariant if for all (x; y) 2 and

all h 2 End(A), h(x); h(y) 2 . We denote by Con(A) the set of fully
invariant congruences of A. It is immediate from the denition that
This equation has several consequences. First, both A and A2 are fully
invariant congruences on A. Second, for any A2, there is a smallest
fully invariant congruence on A containing . We shall write CgA() for

this congruence. Finally, Theorem 2.2 can be applied to compute CgA()

(with F replaced by F [ End(A)).
Parallel to our problem Gen-Con, we dene
With minor modications, Algorithm 1 can be used to compute Gen-Confi.
In light of equation (6), if Algorithm 1 is used to compute Gen-Confi, then
in step 7, g must be chosen from rather than from F(A). But
note that Thus, we provide a modied
algorithm, Algorithm 2, in which this step is replaced with the sequence
7a{7e. The idea behind this sequence of steps is as follows. We rst toss a
coin. If the coin comes up 'heads', we choose g 2 F(A) as before. However,
on 'tails', we guess an arbitrary function g : A ! A and then check to see if
g is an endomorphism of A. If it is, we proceed to step 8. If not, we reject
this instance.
Algorithm
(1) z a, n jAj
(3) Choose z0 2 A
Choose (u; v) 2
do
7a. Toss a coin
7b. If heads then choose g 2 F(A)
7c. else do
7d. Choose
7e. If g 2= End(A) then Reject
od
od
Reject
od
Reject
Unlike the original algorithm, this modied version can not be executed
in log-space. This is because we require enough space to hold the entire
function g whenever the coin comes up 'tails'. Since a function from A to A
is a list of n integers in the range 1g, the space requirement for g
is n log n. In general, this will not be bounded by the logarithm of the size
of the input (see inequality (1)).
However, our modied algorithm does run in (nondeterministic) polynomial
time. The verication that a function g is an endomorphism requires
one pass through each of the tables for the basic operations of the algebra.
Since the algorithm reaches step 7 at most n3 times, the total running time
will be bounded by a polynomial in the size of the input.
As an alternative, one can prove that Gen-Confi 2 NP by observing
that in light of Theorem 2.2, Gen-Confi can be dened by a second-order,
existential sentence. From Fagin's theorem [6] it follows that any language
dened in this way lies in NP.
We now wish to prove that Gen-Confi is hard for NP. We will do this
by reducing the well-known problem Clique to Gen-Confi. For a positive
integer n, let Kn denote the digraph with vertex set f1; ng and (di-
rected) edges f (x; g. If G is a digraph, then a clique of G is asubgraph isomorphic to some Kn. We call G loopless if it has no edges of
the form (x; x). We dene

loopless digraph, n 1,

and G has a clique of size n :
The problem Clique is known to be NP-complete, see [8, p. 194].
"i and digraphs. A homomorphism from H
to G is a function t: H ! G such that (x; y) 2 implies (t(x); t(y)) 2 ".
Note that a loopless graph G has a clique of size n if and only if there is a
homomorphism from Kn to G.
In [10], Hedrln and Pultr described an elegant transformation from digraphs
to unary algebras that has been used several times [2, 15] to reduce
problems involving graphs to similar problems involving algebraic struc-
tures. Given a digraph hG; "i, we shall dene an algebra Gb as follows.
The universe of Gb is the set are points
not appearing in either G or ". are unary
operations dened by
Furthermore, let t: H ! G be a digraph homomorphism. We dene a
function t^: Hb ! Gb given by
Theorem 4.1 (Hedrln and Pultr, [10]). The mappings G ! Gb and t ! t^
constitute a full and faithful functor from the category of digraphs to that
of algebras with two unary operations. In other words, for each pair H,
G of digraphs, and each digraph homomorphism t, the function t^: Hb !
Gb is a homomorphism and furthermore, the mapping t ! t^ is a bijectionbetween the homomorphisms from H to G and the homomorphisms between
Hb and Gb.
It follows that any homomorphism from Hb to Gb must preserve u and v,
and map vertices to vertices and edges to edges.
Lemma 4.2. Clique log Gen-Confi.
Proof. Let hG; ni be an instance of Clique, with "i. Fix a new
vertex a and dene That is, there
is an edge from a to each vertex of G as well as an edge in the opposite
direction. Let denote the disjoint union of the
graphs G0 and K.
Now dene G00 to be G0 +K and set A = Gc00 (see Theorem 4.1). Pick two
distinct vertices a and b from K, and let e be the edge from a to b. Finally,
To complete the proof of the Lemma, we

shall show that
hG;
that is, G has a clique of size n if and only if (a; a) 2 .
Suppose rst that G has a clique of size n. Then G0 has a clique of size
n+1 that includes the vertex a. Therefore, there is a graph homomorphism
t0 from K to G0. Because of the symmetry of K, we can assume that
a. The map t0 can be extended to a graph homomorphism t: G00 !
G00 by mapping each vertex of G0 to itself. Theorem 4.1 yields an (algebra)
homomorphism t^: A ! A. Note that by the denition of t^, we have
Now, using the fact that is a fully invariant congruence, we compute
Conversely, suppose (a; a) 2 . Since A is a unary algebra and Kb is a
subalgebra, by Lemma 3.2 there is a on A. Since
(a; a) 2= , we certainly have * . On the other hand, , so is
not fully invariant. (For otherwise, = Cg() .) It follows that some
endomorphism of A must fail to map Kb to itself. By Theorem 4.1, this
endomorphism is of the form t^, for some t: G00 ! G00, and it must be the
case that t does not map K into itself. But since K is complete and is
disjoint from G0, t must actually map K to G0. Therefore, G0 contains a
clique of size n + 1. At most one of the vertices in the clique can be equal
to a, so we conclude that G has an n-clique.
Theorem 4.3. Gen-Confi is NP-complete
Proof. Our modied version of Algorithm 1 shows that Gen-Confi 2 NP.
Since Clique is NP-complete, it follows from Lemma 4.2 that Gen-Confi
is NP-complete as well.
The notion of \full invariance" can be extended to objects other than
congruences on algebras. For example, let hG; "i be a digraph and
G. Let us call S fully invariant if for every h 2 End(G), h(S) S.
Furthermore dene the fully invariant subset generated by a set S (denoted
SgG(S)) to be the smallest fully invariant subset of G containing S. Notice

that g. We dene two problems:

digraph and S a fully invariant subset g
digraph and a 2 SgG
Using the same ideas as in Theorem 4.3, we can prove the following.
Theorem 4.4. FI-Subset is complete for co-NP. Gen-Subsetfi is complete
for NP.
Proof. Suppose that hG; Si is an instance of FI-Subset. Let P denote
the complement of FI-Subset. To show that S is not fully invariant, we
can guess a function verify that h is an endomorphism and
that h(S) * S. This gives a nondeterministic algorithm for P that runs in
polynomial time. To reduce Clique to P, let G be a loopless graph and n
a positive integer. Let Kn. Then it is easy to see that Kn fails to
be fully invariant in H if and only if there is a (graph) homomorphism from
Kn to G. This in turn is equivalent to the existence of an n-clique in G.
Thus P is NP-complete, and therefore FI-Subset is complete for co-NP.
Now for the second problem. The condition hG;
can be checked by guessing a function G, checking that h is an
endomorphism of G, and that a 2 h(S). To prove that Clique log
Gen-Subsetfi follow the construction given in Lemma 4.2 to produce the
graph G00. Then one easily sees that G has an n-clique if and only if
a 2 SgG 00 (K). Thus Gen-Subsetfi is NP-complete.


--R


Computing congruences eciently
On full embeddings of categories of algebras
Introduction to automata theory
Languages that capture complexity classes

Complete problems for deterministic polynomial time
The computational complexity of some problems in universal algebra
Symmetric space-bounded computation
Categories for the working mathematician
On the general theory of algebraic systems

Computational complexity
Relationships between nondeterministic and deterministic tape com- plexities
Introduction to the theory of computation
Remarks on fully invariant congruences
Universal algebra for computer scientists
Department of Mathematics

Department of Computer Science

--TR
Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
Languages that capture complexity classes
Introduction to the Theory of Computation
Introduction To Automata Theory, Languages, And Computation
Computers and Intractability
Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
simple algebra;nondeterministic log-space;congruence;graph accessibility