---

Universal Algebra and Complexity / Algèbre universelle et complexité
Org: Jennifer Hyndman (UNBC), Benoit Larose (Concordia) and/et Denis Therien (McGill)

---

DAVID MIX BARRINGTON, University of Massachusetts Amherst, Amherst, MA 01003, USA
Complexity for Groupoids Given by Table

Suppose we are given a complete multiplication table for a groupoid (binary algebra) and are asked to evaluate a given product of elements, or determine whether an element is generated by a given set of elements. In general, these problems are complete for the complexity classes LOGCFL (also known as SAC¹) and P respectively, and by restricting the class of groupoids possible we get a variety of other interesting problems. In this talk we survey some results and open problems in this area. In particular, we show how results on the iterated product problem for groups (Barrington-Kadau-Lange-McKenzie 2001) led to the solution of a longstanding open problem about integer division (Hesse-Allender-Barrington 2002).

MARTIN BEAUDRY, Université de Sherbrooke, Sherbrooke, QC J1K 2R1
Finite aperiodic loops as language-recognizing devices

Since it was proved that finite loops recognize exactly the open regular languages, the aperiodic, or group-free, loops have emerged as a promising special case. In particular, the languages they recognize happen to be star-free. This opens the problem of developing a workable characterization of the open star-free languages.

This is joint work with François Lemieux and Denis Thérien.

MANUEL BODIRSKY, Humboldt-Universität zu Berlin
Constraint Satisfaction Problems with Infinite Domains

The complexity of constraint satisfaction problems is intensively studied for finite templates. In this talk I will discuss constraint satisfaction problems with a template over an infinite domain. I focus on templates that are omega-categorical, a well-known concept in model theory. For this class, several techniques known for constraint satisfaction with finite templates still apply-in particular, I will discuss generalizations of well-known Galois-connections, and the notion of a core of a relational structure.

ANDREI BULATOV, Simon Fraser University, Burnaby, Canada
Complexity of constraint counting problems

We consider the problem #CSP(B): given a relational structure A, compute the number of homomorphisms from A to the relational structure B. We give some examples and show the connection between the complexity of #CSP(B) and the polymorphisms of B.

We identify two necessary conditions for the tractability of #CSP(B):

(1) B has a Mal'tsev polymorphism,
(2) every pair of equivalence relations definable in B (congruences of the corresponding algebra Alg(B)) satisfies certain combinatorial conditions.

Finally we show that these conditions are also sufficient for the tractability of #CSP(B) when satisfied by every finite algebra from the variety generated by Alg(B).

VICTOR DALMAU, Universitat Pompeu Fabra
Constraint Satisfaction Problems and the Expressiveness of Finite Algebras

Constraint satisfaction problems arise in a wide variety of domains, such as combinatorics, logic, and artificial intelligence. In recent years, much effort has been directed towards classifying the complexity of all families of constraint satisfaction problems. It has been shown that it is possible to associate to every subclass of the CSP an algebra A such that the complexity the corresponding CSP is completely determined by the properties of A.

Let A be any algebra over a finite universe. We define the expressiveness of A as the mapping ex_A : N ® N that given a natural number n returns the number subuniverses of Aⁿ. Some algebras A that lead to tractable cases of the CSP such as Mal'tsev algebras, or algebras containing a near-unanimity operations among their term operations, satisfy the following property: logex_A (n) £ p(n), for some polynomial p. We call any such algebra polynomially expressible. We conjecture that all polynomially expressible algebras give rise to families of constraint satisfaction problems solvable in polynomial time. In this talk we shall present some initial results in this direction.

RICARD GAVALDA, Universitat Politecnica de Catalunya, Barcelona, Spain
Learnability of functions defined by programs over semigroups

Computational Learning Theory studies the existence of algorithms that provably and efficiently learn classes of functions, under a rigorously defined model of "learning". Learning via queries is one such model, and among the best studied ones: it assumes that an external agent knows one target function from the class, and the learning algorithm must identify that function exactly by asking the agent queries from a predefined set.

In this talk, we survey recent works studying the learnability of classes of functions defined by several variants of programs over monoids or semigroups. In many contexts, it is possible to design learning algorithms that learn whole (and natural) varieties of semigroups, which in turn can compute classes of functions that had been independently studied in Computational Learning Theory. Often, one can show that the limit of learnability (e.g., using a fixed set of query types) coincides exactly with such a variety of semigroups, suggesting a strong connection between the algebraic complexity of semigroups and their learning complexity.

PAVOL HELL, Simon Fraser University, Burnaby, BC V5A 1S6
List Partition Problems

List partition problems are certain restrictions of binary list constraint satisfaction problems. A. Bulatov has recently proved the dichotomy of all list constraint satisfaction problems. The speaker and Tomás Feder used Bulatov's result to prove the following `quasi-dichotomy' for list partition problems:

Each list partition problem is NP-complete or solvable in quasi-polynomial time (of order n^O(logn)).

There are examples of list partition problems for which the best known algorithms have performance n^{O(logn/loglogn)}. (These algorithms are also joint with D. Krá\'l and J. Sgall.)

Variants in which the number of occurences of a variable, and/or the sizes of the lists, are bounded by small constants, will also be discussed.

MIKI HERMANN, LIX, Ecole Polytechnique, France
An Algebraic Approach to the Complexity of Generalized Conjunctive Queries

Constraint satisfaction is recognized as a fundamental problem in artificial intelligence, in automated deduction, in computer-aided verification, in operations research, etc. At the same time conjunctive query containment is considered as a fundamental problem in database query evaluation and optimization. Recent research points out that query containment is a central problem in several database and knowledge base applications, including data warehousing, data integration, query optimization, and (materialized) view maintenance.

Kolaitis and Vardi pointed out that constraint satisfaction and conjunctive query containment are essentially the same problem. Constraints are usually specified by means of relations. The standard constraint satisfaction problem can therefore be parameterized by restricting the set of allowed relations. In particular, given a finite set S of Boolean relations, we consider conjunctive propositional formulas consisting of clauses built over relations from S, also called S-formulas. Deciding the satisfiability of such an S-formula is known as the generalized satisfiability problem, denoted by SAT(S), and was first investigated by Schaefer. It turns out that the complexity of SAT(S) can be characterized by closure properties of S. This correspondence is obtained through a generalization of Galois theory. In order to get complexity results via this algebraic approach, conjunctive queries COQ(S) over a set of relations S turn out to be useful. Roughly speaking, a conjunctive query from COQ(S) is an S-formula with distinguished variables, where all non-distinguished variables are existentially quantified. These queries play an important role in database theory, since they represent a broad class of queries and their expressive power is equivalent to select-join-project queries in relational algebra. Thus they are also of interest in their own right and we study the complexity of some related computational problems. The algebraic approach is particularly well adapted to this study, yielding short and elegant proofs.

We focus here on the counting problem for conjunctive queries. The problem is to count the number of entries in the database that match the query, i.e., the number of satisfying assignments. We obtain a complete complexity classification that indicates a difference with respect to satisfiability problems of Boolean constraints.

Measures such as conditional probability (confidence) and correlation have been used to infer rules of the form "buying diapers causes you to buy beer". However, such rules indicate only a statistical relationship between items, but they do not specify the nature and causality of the relationship. In applications, knowing such causal relationship is extremely useful for enhancing understanding and effecting change. While distinguishing causality from correlation is a truly difficult problem, recent work in statistics and Bayesian learning provide some promising directions of attack.

In this context, the ideas of Bayesian learning, where techniques are being developed to infer casual relationships from observational data, to mining large databases trigger the necessity to study counting problems in connection with existing database applications. Yet another recent application of Bayesian learning based on counting is the task of spam elimination.

Therefore we think that our results will have an impact on concrete database implementations and applications, since the considered formulas in our computational problems correspond better to the model of queries formulated within existing database systems than the so far mainly studied S-formulas.

While the complexity of conjunctive-query evaluation and constraint satisfaction is the same, we determined that this is not any more the case for other computational goals. We have shown that the counting problem for conjunctive queries has a different structure than that for conjunctive formulas. The latter displays a dichotomy behavior between the affine formulas in FP and the #P-complete other cases, whereas the former presents a trichotomy structure between the affine cases in FP, the Horn, dual Horn, and bijunctive #P-complete cases, and finally the general #·NP-complete case. This shows that, under the more fine-grained analysis presented by counting, the conjunctive queries present three different levels of (in)tractability.

This is a joint work with Michael Bauland, Philippe Chapdelaine, Nadia Creignou, and Heribert Vollmer.

ANDREI KROKHIN, University of Durham, Department of Computer Science, Science Labs, South Road, Durham DH1 3LE, UK
Supermodular lattices and the complexity of constraint optimisation

The maximum constraint satisfaction problem (MaxCSP) is an optimisation version of the CSP. In MaxCSP, one is given a collection of constraints on overlapping sets of variables, and the goal is to find an assignment of values to the variables which maximizes the number of satisfied constraints. This problem is NP-hard in general, but, by restricting the set of allowed constraint types, one can obtain a tractable (that is, polynomial-time solvable) problem. This talk is an account of recent progress made in classifying the complexity of MaxCSP with respect to the set of allowed constraints. In particular, we will explain the role played by the condition of supermodularity on finite lattices in attempts to solve the above mentioned classification problem.

The talk is based on joint work with M. Cooper, D. Cohen, P. Jeavons, P. Jonsson, M. Klasson, and B. Larose.

GABOR KUN, Eotvos Lorand University, Pazmany Peter setany 1/c, Budapest, Hungary, H-1117
On the fundamental group and coverings of finite posets

The complexity of the Constraint Satisfaction Problem (CSP) is one of the most examined questions in complexity theory. The known cases of NP-complete CSP's are those relational structures which does not admit any nontrivial idempotent operation. Feder and Vardi have proved that every CSP is polynomial-time equivalent to a poset retraction problem. The typical, known posets admitting no nontrivial idempotent operation are the crowns.

In our talk we introduce a combinatorial definition of the fundamental group of posets. This combinatorial definition leads to the same type-covering theorems than in the case of topological spaces. We give a characterization of posets from those no crown can be obtained using retracts and finite covering posets.

Theorem 1 Let P be a finite connected poset. Then the following conditions are equivalent.

(i) A crown is a retract of a finite covering poset of P.
(ii) The additive group of the integers is the homomorphic image of a finite index subgroup of the fundamental group of P.

FRANCOIS LEMIEUX, Université du Québec à Chicoutimi, 555 boul. de l'Université, Chicoutimi, Québec G7H 2B1
Groupoids that recognize only regular languages

It is known that finite groupoids (finite set closed under a binary operation) can be seen as a model of computation that generalises finite semigroups. The sets they recognize is exactly the class of context-free languages. Previous studies in groupoid theory have made extensive use of the multiplication semigroup of a groupoid G that is the closure under composition of the transformation R_g(x)=xg and L_g(x)=gx for all g Î G. In this talk we will consider those groupoids that can only recognize regular languages.

We prove that any groupoid whose multiplication semigroup belongs to the pseudovariety DO (where the set of idempotents of each regular J-class forms a subsemigroup) can recognize only regular languages. An important subclass of such groupoids is the set of loops whose multiplication semigroup is a group.

We show that any loop that recognizes a language L must be divided by all groups that divide the syntactic monoid of L. Hence, any loop that contains only trivial groups can only recognize languages in AC⁰.

CYNTHIA LOTEN, Simon Fraser University, 8888 University Drive, Burnaby, BC V5A 1S6; University College of the Fraser Valley, 33844 King Road, Abbotsford, BC V2S 7M8
Retractions on Reflexive Graphs

A graph H is called a retract of a graph G if H is a subgraph of G and there is an edge preserving function from G to H that fixes each vertex of H. Such a function is called a retraction.

The question is, given a fixed graph H and an arbitrary supergraph G, when does a retraction from G to H exist? There are no known conditions that are both necessary and sufficient for the existence of retraction, and there are graphs H for which the question is NP-c. However, we can take a necessary condition N, and create a class of graphs H called absolute retracts with respect to N, AR_N, for which N is also a sufficient condition. The various classes of absolute retracts studied are all varieties and can be analyzed using near-unanimity functions, dismantlability, chordal graphs and totally symmetric idempotent functions.

JAROSLAV NESETRIL, Department of Applied Mathematics and Institute of Theoretical Computer Science, Charles University, Prague, Czech Republic
Density, Complexity, Universality

We exhibit a connection of density (of homomorphism order of finite structures) and the complexity of the corresponding Constraint Satisfaction Problems. We survey recent solution of density problem for various classes of structures including oriented trees and planar graphs. This is also related to universality of very special classes of strutures.

The results were obtained jointly with C. Tardif, P. Ossona de Mendez, T.  Luczak and R. Strausz.

STEVE SEIF, Mathematics Department, Univ. of Louisville, Louisville, KY 40292
Word and constraint satisfaction problems

Progress has been made on the question of whether constraint-satisfaction problems on finite sets "admit a dichotomy" using algebraic methods. Essentially the same question exists for word problems for finite algebras. The connection between the two dichotomy questions will be discussed.

HOWARD STRAUBING, Boston College, Chestnut Hill, Massachusetts, USA
C-varieties of Morphisms into Finite Monoids

Eilenberg and Schutzenberger showed how pseudovarieties of finite monoids and semigroups form the foundation in universal algebra for the algebraic theory of finite automata and the languages they accept. Recent results, principally from the domains of circuit complexity, finite model theory and temporal logic, suggest that these foundations are inadequate. We introduce a more general notion, C-varieties of morphisms into finite monoids, that includes the older theory as a special case and accounts for all the new results.

We give the basic definitions and the generalization of Eilenberg's correspondence theorem, and present a theorem that shows how C-varieties arise naturally in first-order logic, temporal logic and circuit complexity. (Preliminary versions of these results were originally announced, without detailed proofs, in 2002.)

We develop the equational theory for C-varieties and semidirect products of C-varieties, and give several applications. This is based on joint work with J. E. Pin and L. Chabard. The equational theory was developed independently by M. Kunc.

CSABA SZABÓ, Eötvös Loránd University, Budapest, 1117 Pázmány Péter sétány I/C
The compexity of solving polynomials over finite algebras

For a finite algebra, A checking an equation (Termeq A) or solving a polynomial (Polsat A) is a classical problem. But the notion of polynomial has a different meaning over a ring or over a ring as a universal algebra. In the first case it is a sum of monomials in the second case it is sums of products of sums of .... For the two element ring Z₂ in the first case the Polsat problem can be solved in polynomial time; in the second case it is NP-complete (J. Lawrence, R. Willard). For the group A₄ both problems are solvable in polynomial time. But if we introduce the commutator as a new operation (why not? the operation table can be obtained at the preprocessing) both problems turn out to be hard (G. Horváth, Cs. Szabó). From now we allow to add finitely many basic operations to the algebra and we look for the "maximal" complexity of the Termeq and Polsat problems, called Termeq* and Polosat*. We characterize the Polsat* problem for congruence modular algebras and the Termeq* problem for groups.

PASCAL TESSON, Université Laval
On the complexity of solving systems over finite semigroups

For a fixed finite semigroup, we consider the problem EQN^*_S of determining whether a system of equations over S has a solution. We show that when S is a monoid, then EQN^*_S is solvable in polynomial-time if S is a commutative union of groups but is NP-complete otherwise. We also show that providing a similar dichotomy result for all finite semigroups would resolve the dichotomy conjecture for constraint satisfaction problems.

JIRI TUMA, Charles University in Prague, Faculty of Mathematics and Physics, Sokolovska 83, 186 00 Prague 8, Czech Republic
Congruence liftings of diagrams

A lifting of a diagram of semilattices and homomorphisms with respect to the functor Con in a variety V is a simultaneous representation of all semilattices as semilattices of compact congruences of algebras in V and all semilattice homomorphisms as the Con values of homomorphisms between the representing algebras in V. We present a small diagram D of Boolean subsemilattices of the semilattices 2⁴ such that no variety V allowing a lifting satisfies a non-trivial congruence identity. This is a joint work of F. Wehrung and J. Tuma.

MATT VALERIOTE, McMaster University, Hamilton Ontario, Canada
Tractable Algebras and Congruence Distributivity

A finite algebra A is said to be tractable if the collection of all subuniverses of finite powers of A forms a tractable constraint language. It is conjectured by Bulatov, Jeavons, and Krokhin that a finite idempotent algebra A is tractable if and only if the equational class generated by A omits the unary type from Tame Congruence Theory.

The property of an algebra having bounded relational width was introduced by Bulatov and Jeavons and is closely related to the concept of bounded width developed by Feder and Vardi. The satisfaction of either property by a finite algebra ensures that it is tractable. It is conjectured that a finite idempotent algebra A has bounded relational width if and only if the equational class generated by A omits both the unary and affine types. Algebras that generate congruence distributive equational classes are examples of algebras of this kind.

In my talk I will discuss the bounded relational width conjecture and in particular the results of Larose and Zadori relating to it. I will also discuss progress made towards determining whether or not finite algebras in congruence distributive equational classes have bounded relational width.

ROSS WILLARD, University of Waterloo, Waterloo, Ontario N2L 3G1
Finitely axiomatizable varieties and pseudo-varieties

I report on recent work on an open problem of S. Eilenberg and M. Schützenberger from 1976, recently revived by G. McNulty, namely: if the pseudo-variety HSP_fin (A) generated by a finite algebra is finitely axiomatizable (i.e., relative to the axiom "I am finite"), does it follow that the variety HSP(A) generated by A is also finitely axiomatizable?