Kudryavtsev V.B., Rosenberg I.G. Structural Theory of Automata, Semigroups, and Universal Algebra

Подождите немного. Документ загружается.

Endoprimal algebras 175

4 Abelian groups

Throughout this section, group will mean abelian group. We shall use the notations Z, Z

and Q for the (additive) groups (or sometimes, by abuse, for the sets or rings) of integers,

integers mod n, and rational numbers, respectively. The letter p will denote an arbitrary

prime number. For undeﬁned notions and notations concerning groups we refer to [9]. Recall

that the term functions of abelian groups are the functions of the form f(x

,...,x

+ ···+ k

with some integers k

,...,k

We begin by giving some easy obstacles to endoprimality of a group; these were established

in [14]. All results in this section are due to K. Kaarli and L. M´arki, in some cases with other

co-authors.

4.1 Proposition If a torsion-free group is p-divisible for a prime p then the group is not

endoprimal.

Indeed, in such a group the function f (x)=x/p is an endofunction but not a term

function.

4.2 Proposition [14, Proposition 2.1] If End A is isomorphic to a subring of Q then the

group A is not endoprimal.

In fact, if End A is isomorphic to a subring of Q then A must be a torsion-free group,

and the function

f(x, y)=



0ify =0,

x if y =0

in A is an endofunction but not a term function. Consequently, no torsion-free group of

rank 1 is endoprimal.

If the centre of a ring R consists only of integral multiples of the identity map 1

then

we say that the centre of R is trivial.

4.3 Proposition A group whose endomorphism ring has non-trivial centre cannot be endo-

primal.

Indeed, any central element of the endomorphism ring is a unary endofunction, and if a

central element is not trivial (i.e., not of the form nx for some n ∈ Z)thenitisnotaterm

function.

It is a very useful observation that endofunctions of a direct sum of two groups are sums

of endofunctions of the direct summands. If there are no non-trivial homomorphisms between

these summands, then endoprimality reduces even beyond endoprimality of the summands.

4.4 Proposition [14, Corollary 2.6] Let A be the direct sum of nonzero groups B and C with

Hom(B, C)=Hom(C, B)=0.ThenA is endoprimal if and only if B and C are bounded

and endoprimal.

Let us show how boundedness (that is, having ﬁnite exponent) comes into play. If, say, B

is unbounded then the function f = f|

+f |

with f|

,andf|

= 0, is an endofunction

of A which is not a term function. On the other hand, if both B and C are bounded then

176 K. Kaarli and L. M´arki

the Chinese Remainder Theorem applies to show that every pair of n-ary term functions of

the components is induced by a common (n-ary) term.

Let us give also a ‘prototype’ of examples for endoprimal groups.

4.5 Theorem [14, Theorem 2.7] Let A be the direct sum of a group B and the inﬁnite cyclic

group Z.ThenA is endoprimal if and only if B is not bounded.

Heuristically, in the case when B is unbounded, the proof relies on the fact that Z maps

‘everywhere’ in B via endomorphisms. This forces both f|

and f|

to be term functions for

any endofunction f in A, and then, by the unboundedness of B, these two term functions

must coincide.

Here are the main results of [14].

4.6 Theorem [14, Theorem 3.1] A torsion group A is endoprimal if and only if it is bounded,

say of exponent m,andZ

⊕ Z

embeds into A.

(For bounded groups, this was proved earlier by B. A. Davey and J. Pitkethly [7].)

To present results on the torsion-free case, we recall the deﬁnitions of some well-known

notions. By χ(a) we denote the characteristic sequence of the element a (i.e., the sequence

of the p-heights of a under a ﬁxed ordering of the primes). The members of such a sequence

are non-negative integers and ∞. Two characteristic sequences are said to be equivalent if

they diﬀer only at ﬁnitely many places, and not at places where ∞ occurs. The equivalence

classes of characteristic sequences are called types.Thetypet(a)ofanelementa is the type

containing χ(a). It is well known that all nonzero elements of a torsion-free group A of rank 1

have the same type. This type is denoted by t(A). Conversely, every type can be realised

as the type of a torsion-free group of rank 1. Clearly, the natural (placewise) ordering of

characteristic sequences carries over to an ordering of types.

4.7 Theorem [14, Theorem 4.1] Let a torsion-free group A decompose into A = B ⊕ C

where B is nontrivial, C has rank 1 and its type does not contain inﬁnity, and suppose that

t(C) ≤ t(b) for every b ∈ B.ThenA is endoprimal.

4.8 Theorem [14, Theorem 4.3] A torsion-free group A of rank 2 is endoprimal if and only

if A = B ⊕ C where B and C are groups of rank 1, t(B) ≥ t(C),a

ndC (or, equivalently,

A) is not p-divisible for any prime p.

For mixed groups the following was obtained in [14]. Recall that a p-group is reduced if

and only if it does not contain the Pr¨ufer group Z

∞

4.9 Theorem [14, Corollary 5.5] If the torsion part T of a mixed group A is bounded (in

which case T is a direct summand of A) then A is endoprimal if and only if A/T is endo-

primal.

In [14] the endoprimality problem was also solved for groups of torsion-free rank 1 with

splitting torsion part. Since this result was later generalised to the non-splitting case (see

Theorem 4.12), we do not formulate it here.

Endoprimal algebras 177

Thus we see that all major results of [14] relate to groups which have a suitable direct

decomposition. In view of this fact and the above results, the following classes of groups

come into question for a complete description of their endoprimal members.

(1) Torsion-free groups which decompose into a direct sum of rank 1 groups.

(2) Torsion-free groups of rank 3.

(3) Mixed groups whose maximal torsion-free factor group has rank 1.

Recently we have managed to settle all these cases.

For case (1) the problem could be solved for an even larger class of groups by R. G¨obel,

K. Kaarli, L. M´arki, and S. L. Wallutis [10]. To state the result, we need the following

deﬁnitions.

A torsion-free group A is said to be separable if every ﬁnite subset of A is contained in

some direct summand of A which decomposes into a direct sum of rank 1 groups. If A is a

separable torsion-free group then a type τ is said to be critical for A if A has a rank-1 direct

summand of type τ. The set of critical types for a group A will be denoted by T

(A).

For a set T of types we deﬁne the type graph of T ,Γ(T ), to be the undirected graph with

T as the set of vertices and edges (τ

,τ

) for comparable τ

,τ

∈ T , i.e. τ

≤ τ

or τ

≤ τ

Recall that a graph is said to be connected if between any two vertices there is a ﬁnite path.

4.10 Theorem [10, Theorem 9] Let A be a torsion-free separable group and T = T

(A) be

the set of all critical types of A.ThenA is endoprimal if and only if rk(A) ≥ 2, A is not

p-divisible for any prime p, and the type graph Γ(T ) is connected.

So far, all endoprimal groups we have seen admit ‘good’ direct decompositions. This is

not a must, however: in [10] it is shown that there exist endoprimal indecomposable groups of

arbitrarily large cardinality. The proof relies on a construction of R. G¨obel and S. Shelah [11].

On the other hand, since any proper subring R of Q can be realised as the endomorphism ring

of torsion-free groups of arbitrarily large cardinality, Proposition 4.1 tells us that there are

indecomposable torsion-free groups of arbitrarily large cardinality which are not endoprimal.

This leads to the (sad?) conclusion that it is hopeless to ﬁnd a reasonable description of all

endoprimal abelian groups.

In case (2), the following was proved by K. Kaarli and K. Metsalu [16].

4.11 Theorem [16, Theorem 1.1] Let A be a torsion-free abelian group of rank 3.Thenone

of the following cases occurs:

(1) the group A is endoprimal;

(2) the group A is p-divisible for some prime p and therefore A is not endoprimal;

(3) End A is a subring of Q and therefore A is not endoprimal;

(4) End A has non-trivial centre and therefore A is not endoprimal;

(5) End A is an abelian group of rank 3 and there exist linearly independent elements

∈ A, endomorphisms φ, ψ ∈ End A and u ∈ Q such that φ(a

)=a

φ(a

)=φ(a

)=0, ψ(a

)=ua

, ψ(a

)=ψ(a

)=0;thenA is not endoprimal.

178 K. Kaarli and L. M´arki

Notice that cases 2–4 present general necessary conditions for a group to be endoprimal.

Hence it is ‘almost true’ that a torsion-free group of rank 3 is endoprimal unless there is an

obvious obstacle to its endoprimality. It may be surprising that, even for these groups of

small rank, decomposability is not a necessary condition of endoprimality: in [16] an example

is constructed for an endoprimal indecomposable torsion-free group of rank 3.

A large part of the proof of Theorem 4.11 goes through for torsion-free groups of arbitrary

ﬁnite rank, so at least ‘reasonable’ partial results can be hoped for in that fairly general

situation.

Finally, the question of endoprimality for mixed groups whose maximal torsion-free factor

group has rank 1 was settled by K. Kaarli and L. M´arki [15]. The result reads as follows.

4.12 Theorem [15, Theorem 1.2] Let A be a group with torsion part T and P be the set

of those primes p for which A/T is p-divisible. Assume A has torsion-free rank 1.ThenA

is endoprimal if and only if T is unbounded and, for every p ∈ P ,thep-component of T is

either not reduced or it is not a direct summand of A.

Notice that we also get endoprimal groups of this kind in which none of the primary parts

splits oﬀ; in other words, such groups are as ‘close to being indecomposable’ as a mixed group

of torsion-free rank 1 can be.

5 Other classes of algebras

We survey here the known endoprimality results for sets, vector spaces, semilattices, and

implications algebras.

We have already mentioned Sangalli’s result [22] that all but 2-element sets are endo-

primal. The 2-element set is not endoprimal because the transposition of its elements is an

endofunction but not a term function.

Using the duality theory approach it is easy to show that all but 1-dimensional ﬁnite

vector spaces are endoprimal. B. A. Davey and J. G. Pitkethly [7] extended this result

to inﬁnite vector spaces. The underlying idea was that all vector spaces are free algebras.

Another possible way to get the same result is to rewrite the proof of Theorem 4.5 for vector

spaces. Thus we have the following theorem.

5.1 Theorem [7, Theorem 2.4] A vector space is endoprimal if and only if its dimension is

not 1.

Now we formulate the result for semilattices, which again was obtained by B. A. Davey

and J. G. Pitkethly [7] using a mixture of duality and non-duality theory methods.

5.2 Theorem [7, Theorem 5.2] A non-trivial semilattice is endoprimal if and only if it is

not a tree.

Note that in this theorem we did not assume that the signature of the semilattice includes

bound(s) 0, 1 or both. If there is at least one bound then the result may be slightly diﬀerent.

For example, a non-trivial bounded semilattice is endoprimal if and only if it is not a chain.

Endoprimal algebras 179

Endoprimal implication algebras were completely characterised in the recent paper [21]

by J. G. Pitkethly. Recall that an implication algebra can be deﬁned as a groupoid with a

binary operation → satisfying the identities:

(x → y) → x = x, (x → y) → y =(y → x) → x, x → (y → z)=y → (x → z).

It is known that every implication algebra is a semilattice with respect to the term operation

x ∨ y =(x → y) → y.

5.3 Theorem [21, Theorem 2.5] An implication algebra A is endoprimal if and only if for

every n ≥ 1 there exist a

,...,a

∈ A such that the set {



j=i

| i ∈{1,...,n}} does not

have a lower bound in A; ∨.

Note that this result cannot be obtained by using duality theory.

References

[1] D.M.ClarkandB.A.Davey,Natural Dualities for the Working Algebraist, Cambridge

University Press, Cambridge, 1998.

[2] B. A. Davey, Duality for equational classes of Brouwerian and Heyting algebras, Trans.

Amer. Math. Soc. 221 (1976), 119–146.

[3] B. A. Davey, Dualisability in general and endodualisability in particular, in: Logic and

Algebra (Proc. Conf. Pontignano, 1994), (A. Ursini, P. Agliano, eds.), Lecture Notes in

Pure and Appl. Math. 180, Marcel Dekker, New York, 1996, 437–455.

[4] B. A. Davey, M. Haviar, and H. A. Priestley, Endoprimal distributive lattices are endo-

dualisable, Algebra Universalis 34 (1995), 444–453.

[5] B. A. Davey, M. Haviar, and H. A. Priestley, The syntax and semantics of entailment in

duality theory, J. Symbolic Logic 60 (1995), 1087–1114.

[6] B. A. Davey, M. Haviar, and H. A. Priestley, Kleene algebras: a case-study of clones

and dualities from endomorphisms, Acta Math. Sci. (Szeged) 67 (2001), 77–103.

[7] B. A. Davey and J. G. Pitkethly, Endoprimal algebras, Algebra Universalis 38 (1997),

266–288.

[8] B. A. Davey and H. Werner, Piggyback-Dualit¨aten, Bull. Austral. Math. Soc. 32 (1985),

1–32.

[9] L. Fuchs, Inﬁnite Abelian Groups, I–II, Academic Press, New York, 1970, 1973.

[10] R. G¨obel, K. Kaarli, L. M´arki, and S. Wallutis, Endoprimal torsion-free separable abelian

groups, J. Algebra Appl. 3 (2004), 61–73.

[11] R. G¨obel and S. Shelah, Uniquely transitive torsion-free abelian groups, in: Rings, Mod-

ules, Algebras, and Abelian Groups (Proc. Conf. Venice, 2002) (A. Facchini, E. Houston,

and L. Salce, eds.), Lecture Notes in Pure and Appl. Math. 236, Marcel Dekker, New

York, 2004, 271–290.

180 K. Kaarli and L. M´arki

[12] M. Haviar and H. A. Priestley, Endoprimal and endodualisable ﬁnite double Stone alge-

bras, Algebra Universalis 42 (1999), 107–130.

[13] M. Haviar and H. A. Priestley, A criterion for a ﬁnite endoprimal algebra to be endo-

dualisable, Algebra Universalis 42 (1999), 183–193.

[14] K. Kaarli and L. M´arki, Endoprimal abelian groups, J. Austral. Math. Soc. (Series A)

67 (1999), 412–428.

[15] K. Kaarli and L. M´arki, Endoprimal abelian groups of torsion-free rank 1, Rend. Semin.

Mat. Univ. Padova,toappear.

[16] K. Kaarli and K. Metsalu, On endoprimality of torsion-free abelian groups of rank 3,

Acta Math. Hungar. 104 (2004), 271–289.

[17] K. Kaarli and A. F. Pixley, Polynomial Completeness in Algebraic Systems, Chapman

& Hall/CRC, Boca Raton, 2001.

[18] K. Kaarli and H. A. Priestley, Endoprimality without duality, Algebra Universalis 51

(2004), 361–372.

[19] L. A. Kaluˇznin and R. P¨oschel, Funktionen- und Relationenalgebren. Ein Kapitel der

diskreten Mathematik,Lehrb¨ucher und Monographien aus dem Gebiete der exakten Wis-

senschaften, VEB Deutscher Verlag der Wissenschaften, Berlin, 1979.

[20] L. M´arki and R. P¨oschel, Endoprimal distributive lattices, Algebra Universalis 30 (1993),

272–274.

[21] J. G. Pitkethly, Endoprimal implication algebras, Algebra Universalis 41 (1999), 201–

211.

[22] A. A. L. Sangalli, The degree of invariancy of a bicentrally closed clone, in: Lattices,

Semigroups, and Universal Algebra (Proc. Conf. Lisbon, 1988), Plenum Press, New York,

1990, 279–283.

The complexity of constraint satisfaction:

an algebraic approach

Andrei KROKHIN

Department of Computer Science

University of Durham

Durham, DH1 3LE

Andrei BULATOV

School of Computer Science

Simon Fraser University

Burnaby BC, V5A 1S6

Canada

Peter JEAVONS

Computing Laboratory

University of Oxford

Oxford OX1 3QD

Notes taken by Alexander SEMIGRODSKIKH

Abstract

Many computational problems arising in artiﬁcial intelligence, computer science and

elsewhere can be represented as constraint satisfaction and optimization problems. In

this survey paper we discuss an algebraic approach that has proved to be very successful

in studying the complexity of constraint problems.

1 Constraint satisfaction problems

The constraint satisfaction problem (CSP) is a powerful general framework in which a va-

riety of combinatorial problems can be expressed [20, 59, 61, 79]. The aim in a constraint

satisfaction problem is to ﬁnd an assignment of values to the variables, subject to speciﬁed

constraints. In artiﬁcial intelligence, this framework is widely acknowledged as a conve-

nient and eﬃcient way of modelling and solving a number of real-world problems such as

planning [48] and scheduling [75], frequency assignment problems [27], image processing [63],

programming language analysis [65] and natural language understanding [2]. In database the-

ory, it has been shown that the key problem of conjunctive-query evaluation can be viewed as

181

V. B. Kudryavtsev and I. G. Rosenberg (eds.),

Structural Theory of Automata, Semigroups, and Universal Algebra, 181–213.

182 A. Krokhin, A. Bulatov, and P. Jeavons

a constraint satisfaction problem [35, 54]. Furthermore, some central problems in combina-

torial optimization can be represented as constraint problems [20, 30, 42, 50]. Finally, CSPs

have attracted much attention in complexity theory because various versions of CSPs lie at

the heart of many standard complexity classes, and because, despite their great expressive-

ness, they tend to avoid “intermediate” complexity; that is, they tend to be either tractable

or complete for standard complexity classes [7, 8, 9, 11, 13, 20, 30, 51, 46, 73]. On a more

practical side, constraint programming is a rapidly developing area with its own international

journal and an annual international conference, and with new programming languages being

speciﬁcally designed (see, e.g., [61]).

The standard toy example of a problem modelled as a constraint satisfaction problem is

the “8-queens” problem: place eight queens on a chess board so that no queen can capture

any other one [79]. One can think of the horizontals of the board as variables, and the

verticals as the possible values, so that assigning a value to a variable means placing a queen

on the corresponding square of the board. The fact that no queen must be able to capture

any other queen can be represented as a collection of binary constraints C

, one for each pair

of variables i, j, where the constraint C

allows only those pairs (k,l) such that a queen at

position (i, k) cannot capture a queen at position (j, l). It is easy to see that every solution

of this constraint satisfaction problem corresponds to a “legal” placing of the 8 queens.

We now give a formal deﬁnition of the general CSP.

1.1 Deﬁnition An instance of a constraint satisfaction problem is a triple (V,D,C)where

• V is a ﬁnite set of variables,

• D is a set of values (sometimes called a domain), and

•Cis a set of constraints {C

,...,C

}, in which each constraint C

is a pair s

,

 with

a list of variables of length m

, called the constraint scope,and

an m

-ary relation

over the set D called the constraint relation.

The question is whether there exists a solution to (V,D,C), that is, a function from V to

D such that, for each constraint in C, the image of the constraint scope is a member of the

constraint relation.

Now we give some examples of natural problems and their representations as CSPs.

1.2 Example The most obvious algebraic example of a CSP is the problem of solving a

system of equations: given a system of linear equations over a ﬁnite ﬁeld F ,doesithavea

solution? Clearly, in this example each individual equation is a constraint, where the variables

in the equation form the scope, and the set of all tuples corresponding to solutions of this

equation is the constraint relation.

1.3 Example An instance of the standard propositional 3-Satisfiability problem [32, 66]

is speciﬁed by giving a formula in propositional logic consisting of a conjunction of clauses,

each containing three literals (that is, variables or negated variables), and asking whether

there are values for the variables which make the formula true.

Suppose that Φ = φ

∧···∧φ

is such a formula, where the φ

are clauses. The satisﬁability

question for Φ can be expressed as the instance (V, {0, 1}, C) of CSP, where V is the set of

The complexity of constraint satisfaction 183

all variables appearing in the formula, and C is the set of constraints {s

,

,...,s

,

},

where each constraint s

,

 is constructed as follows: s

is a list of the variables appearing

in φ

and 

consists of all tuples that make φ

true. The solutions of this CSP instance

are exactly the assignments which make the formula φ true. Hence, any instance of 3-

Satisfiability can be expressed as an instance of CSP.

Example 1.3 suggests that any instance of CSP can be represented in a logical form.

Indeed, using the standard correspondence between relations and predicates, one can rewrite

an instance of CSP as a ﬁrst-order formula 

) ∧···∧

)wherethe

(1 ≤ i ≤ q)are

predicates on D and 

)means

applied to the tuple s

of variables. The question then

would be whether this formula is satisﬁable [74]. In this paper we will sometimes use this

alternative logical form for the CSP. This form is commonly used in database theory because

it corresponds so closely to conjunctive query evaluation [54], as the next example indicates.

1.4 Example A relational database is a ﬁnite collection of tables. A table consists of a

scheme and an instance,where

A scheme is a ﬁnite set of attributes, where each attribute has an associated set of possible

values, referred to as a domain.

An instance is a ﬁnite set of rows, where each row is a mapping that associates with each

attribute of the scheme a value in its domain.

A standard problem in the context of relational databases is the Conjunctive Query

Evaluation problem [35, 54]. In this problem we are asked if a conjunctive query to a

relational database, that is, a query of the form 

∧···∧

where the 

,...,

are atomic

formulas, has a solution.

A conjunctive query over a relational database corresponds to an instance of CSP by a

simple translation of terms: ‘attributes’ have to be replaced with ‘variables’, ‘tables’ with

‘constraints’, ‘scheme’ with ‘scope’, ‘instance’ with ‘constraint relation’, and ‘rows’ with ‘tu-

ples’. Hence a conjunctive query is equivalent to a CSP instance whose variables are the

variables of the query. For each atomic formula 

in the query, there is a constraint C such

that the scope of C is the list of variables of 

and the constraint relation of C is the set of

models of 

Another important reformulation of the CSP is the Homomorphism problem: the ques-

tion of deciding whether there exists a homomorphism between two relational structures

(see [30, 35, 54]). Let τ =(R

,...,R

) be a signature, that is, a list of relation names with

a ﬁxed arity assigned to each name. Let A =(A; R

,...,R

)andB =(B; R

,...,R

)be

relational structures of signature τ. A mapping h : A → B is called a homomorphism from

A to B if, for all 1 ≤ i ≤ k,(h(a

),...,h(a

)) ∈ R

whenever (a

,...,a

) ∈ R

.Inthis

case we write h : A→B. To see that the Homomorphism problem is the same as the CSP,

think of the elements in A as variables, the elements in B as values, tuples in the relations

of A as constraint scopes, and the relations of B as constraint relations. Then, clearly, the

solutions to this CSP instance are precisely the homomorphisms from A to B.

We now give some more examples of well-known combinatorial problems and their repre-

sentations as a CSP. For the sake of brevity, we use the homomorphism form of the CSP.

184 A. Krokhin, A. Bulatov, and P. Jeavons

1.5 Example For any positive integer k, an instance of the Graph k-Colorability prob-

lem consists of a graph G. The question is whether the vertices of G can be coloured with k

colours in such a way that adjacent vertices receive diﬀerent colours.

It follows that every instance of Graph colorability canbeexpressedasaCSPin-

stance where A = G and B is the complete graph on k vertices, K

1.6 Example An instance of the Clique problem consists of an undirected graph G and an

integer k. The question is whether G has a clique of size k (that is, a subgraph isomorphic

to the complete graph K

It follows that every instance of the Clique problem can be expressed as a CSP instance

where A is K

and B is the graph G.

1.7 Example An instance of the Hamil tonian Circuit problem consists of a graph G =

(V ; E). The question is whether there is a cyclic ordering of V such that every pair of

successive nodes in V is adjacent in G.

It follows that every instance of the Hamiltonian Circuit problem can be expressed as

aCSPinstancewithA =(V ; C

, =

)andB =(V ; E,=

), where =

denotes the disequality

relation on V and C

is the graph of an arbitrary cyclic permutation on V .

1.8 Example An instance of the Graph Isomorphism problem consists of two graphs,

G =(V ; E)andG



=(V



; E



), with |V | = |V



|. The question is whether there is a bijection

between V and V



such that adjacent vertices in G are mapped to adjacent vertices in G



and non-adjacent vertices are mapped to non-adjacent vertices.

It follows that every instance of the Graph Isomorphism problem can be expressed as

aCSPinstancewithA =(V ; E,

E)andB =(V



; E



, E



), where E denotes the set of all pairs

in =

that are not in E.

Many other examples of well-known problems expressed as CSPs can be found further on

in this paper, and also in [42].

2 Related constraint problems

As with many other computational problems, it is not only the standard version of the CSP

(that is, deciding whether a CSP instance has a solution or not) which is of interest. There

are many related problems that have been studied, and in this section we give a brief overview

of some of these.

• Counting Problem

How many solutions does a given CSP instance have?

A standard natural problem associated with many computational decision problems

[20].

• Quantiﬁed Problem

Given a fully quantiﬁed instance of CSP, is it true?

Problems of this form have provided several fundamental examples of PSPACE-compl-

ete problems [20, 22, 74]. Any instance of the ordinary CSP can be viewed as an instance

of this problem in which all the quantiﬁers are existential.