We study the use of local consistency methods as reductions between constraint satisfaction problems (CSPs), and promise version thereof, with the aim to classify these reductions in a similar way as the algebraic approach classifies gadget reductions between CSPs. This research is motivated by the requirement of more expressive reductions in the scope of promise CSPs. While gadget reductions are enough to provide all necessary hardness in the scope of (finite domain) non-promise CSP, in promise CSPs a wider class of reductions needs to be used.

Abstract We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with each other by sending messages through fixed communication channels. Our results endorse the well-known fact from classical CSPs that the complexity of fixed-template computational problems depends on the template’s invariance under certain operations. Specifically, we show that DCSP(Γ) is polynomial-time tractable if and only if Γ is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP(Γ) in finite time. We also show that the same condition holds for the search variant of DCSP. Collaterally, our results unveil a feature of the processes’ neighbourhood in a distributed network, its iterated degree, which plays a major role in the analysis. We explore this notion establishing a tight connection with the basic linear programming relaxation of a CSP.

Abstract. This paper describes several cases of adjunction in the homomorphism preorder of relational structures. We say that two functors [Formula: see text] and [Formula: see text] between thin categories of relational structures are adjoint if for all structures [Formula: see text] and [Formula: see text], we have that [Formula: see text] maps homomorphically to [Formula: see text] if and only if [Formula: see text] maps homomorphically to [Formula: see text]. If this is the case, [Formula: see text] is called the left adjoint to [Formula: see text] and [Formula: see text] the right adjoint to [Formula: see text]. Foniok and Tardif [ Discrete Math., 338 (2015), pp. 527–535] described some functors on the category of digraphs that allow both left and right adjoints. The main contribution of Foniok and Tardif is a construction of right adjoints to some of the functors identified as right adjoints by Pultr [ Reports of the Midwest Category Seminar IV, Lecture Notes in Math. 137, Springer, 1970, pp. 100–113]. We generalize results of Foniok and Tardif to arbitrary relational structures, and coincidently, we also provide more right adjoints on digraphs, and since these constructions are connected to finite duality, we also provide a new construction of duals to trees. Our results are inspired by an application in promise constraint satisfaction—it has been shown that such functors can be used as efficient reductions between these problems.

The fitting problem for conjunctive queries (CQs) is the problem to construct a CQ that fits a given set of labeled data examples. When a fitting CQ exists, it is in general not unique. This leads us to proposing natural refinements of the notion of a fitting CQ, such as most-general fitting CQ, most-specific fitting CQ, and unique fitting CQ. We give structural characterizations of these notions in terms of (suitable refinements of) homomorphism dualities, frontiers, and direct products, which enable the construction of the refined fitting CQs when they exist. We also pinpoint the complexity of the associated existence and verification problems, and determine the size of fitting CQs. We study the same problems for UCQs and for the more restricted class of tree CQs.

We study the power of the bounded-width consistency algorithm in the context of the fixed-template Promise Constraint Satisfaction Problem (PCSP). Our main technical finding is that the template of every PCSP that is solvable in bounded width satisfies a certain structural condition implying that its algebraic closure-properties include weak near unanimity polymorphisms of all large arities. While this parallels the standard (non-promise) CSP theory, the method of proof is quite different and applies even to the regime of sublinear width. We also show that, in contrast with the CSP world, the presence of weak near unanimity polymorphisms of all large arities does not guarantee solvability in bounded width. The separating example is even solvable in the second level of the Sherali-Adams (SA) hierarchy of linear programming relaxations. This shows that, unlike for CSPs, linear programming can be stronger than bounded width. A direct application of these methods also show that the problem of q-coloring p-colorable graphs is not solvable in bounded or even sublinear width, for any two constants p and q such that 3 ≤ p ≤ q. Turning to algorithms, we note that Wigderson's algorithm for -coloring 3-colorable graphs with n vertices is implementable in width 4. Indeed, by generalizing the method we see that, for any ∊ > 0 smaller than 1/2, the optimal width for solving the problem of O(n∊)-coloring 3-colorable graphs with n vertices lies between n1–3∊ and n1–2∊. The upper bound gives a simple exp(Θ(n1–2∊ log(n)))-time algorithm that, asymptotically, beats the straightforward exp(Θ(n1–∊)) bound that follows from partitioning the graph into O(n∊) many independent parts each of size O(n1–∊).

We answer the question of which conjunctive queries are uniquely characterized by polynomially many positive and negative examples and how to construct such examples efficiently. As a consequence, we obtain a new efficient exact learning algorithm for a class of conjunctive queries. At the core of our contributions lie two new polynomial-time algorithms for constructing frontiers in the homomorphism lattice of finite structures. We also discuss implications for the unique characterizability and learnability of schema mappings and of description logic concepts.

We answer the question of which conjunctive queries are uniquely characterized by polynomially many positive and negative examples, and how to construct such examples efficiently. As a consequence, we obtain a new efficient exact learning algorithm for a class of conjunctive queries. At the core of our contributions lie two new polynomial-time algorithms for constructing frontiers in the homomorphism lattice of finite structures. We also discuss implications for the unique characterizability and learnability of schema mappings and of description logic concepts.

Given a pair of graphs $\textbf{A}$ and $\textbf{B}$, the problems of deciding whether there exists either a homomorphism or an isomorphism from $\textbf{A}$ to $\textbf{B}$ have received a lot of attention. While graph homomorphism is known to be NP-complete, the complexity of the graph isomorphism problem is not fully understood. A well-known combinatorial heuristic for graph isomorphism is the Weisfeiler-Leman test together with its higher order variants. On the other hand, both problems can be reformulated as integer programs and various LP methods can be applied to obtain high-quality relaxations that can still be solved efficiently. We study so-called fractional relaxations of these programs in the more general context where $\textbf{A}$ and $\textbf{B}$ are not graphs but arbitrary relational structures. We give a combinatorial characterization of the Sherali-Adams hierarchy applied to the homomorphism problem in terms of fractional isomorphism. Collaterally, we also extend a number of known results from graph theory to give a characterization of the notion of fractional isomorphism for relational structures in terms of the Weisfeiler-Leman test, equitable partitions, and counting homomorphisms from trees. As a result, we obtain a description of the families of CSPs that are closed under Weisfeiler-Leman invariance in terms of their polymorphisms as well as decidability by the first level of the Sherali-Adams hierarchy.

We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with each other by sending messages through fixed communication channels. Our results endorse the well-known fact from classical CSPs that the complexity of fixed-template computational problems depends on the template’s invariance under certain operations. Specifically, we show that DCSP(Γ) is polynomial-time tractable if and only if Γ is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP(Γ) in finite time. We also show that the same condition holds for the search variant of DCSP. Collaterally, our results unveil a feature of the processes' neighbourhood in a distributed network, its iterated degree, which plays a major role in the analysis. We explore this notion establishing a tight connection with the basic linear programming relaxation of a CSP.

Ontology-mediated querying and querying in the presence of constraints are two key database problems where tuple-generating dependencies (TGDs) play a central role. In ontology-mediated querying, TGDs can formalize the ontology and thus derive additional facts from the given data, while in querying in the presence of constraints, they restrict the set of admissible databases. In this work, we study the limits of efficient query evaluation in the context of the above two problems, focusing on guarded and frontier-guarded TGDs and on UCQs as the actual queries. We show that a class of ontology-mediated queries (OMQs) based on guarded TGDs can be evaluated in FPT iff the OMQs in the class are equivalent to OMQs in which the actual query has bounded treewidth, up to some reasonable assumptions. For querying in the presence of constraints, we consider classes of constraint-query specifications (CQSs) that bundle a set of constraints with an actual query. We show a dichotomy result for CQSs based on guarded TGDs that parallels the one for OMQs except that, additionally, FPT coincides with PTime combined complexity. The proof is based on a novel connection between OMQ and CQS evaluation. Using a direct proof, we also show a similar dichotomy result, again up to some reasonable assumptions, for CQSs based on frontier-guarded TGDs with a bounded number of atoms in TGD heads. Our results on CQSs can be viewed as extensions of Grohe's well-known characterization of the tractable classes of CQs (without constraints). Like Grohe's characterization, all the above results assume that the arity of relation symbols is bounded by a constant. We also study the associated meta problems, i.e., whether a given OMQ or CQS is equivalent to one in which the actual query has bounded treewidth.

The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have demonstrated to play a crucial role in many of those applications. For instance, in the decision CSPs, structural properties of the relational structures involved---like, for example, dismantlability---and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. Topological properties of the solution set such as connectedness are related to the hardness of CSPs over random structures. Additionally, in approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions and free energy. In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by Brightwell and Winkler, who showed that dismantlability of the target graph, connectedness of the set of homomorphisms, and good mixing properties of the corresponding spin system are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by Brice\~no. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by Larose, Loten, and Tardif.

We consider the feature-generation task wherein we are given a database with entities labeled as positive and negative examples, and the goal is to find feature queries that allow for a linear separation between the two sets of examples. We focus on conjunctive feature queries, and explore two fundamental problems: (a) deciding whether separating feature queries exist (separability), and (b) generating such queries when they exist. In the approximate versions of these problems, we allow a predefined fraction of the examples to be misclassified. To restrict the complexity of the generated classifiers, we explore various ways of regularizing (i.e., imposing simplicity constraints on) them by limiting their dimension, the number of joins in feature queries, and their generalized hypertree width (ghw). Among other results, we show that the separability problem is tractable in the case of bounded ghw; yet, the generation problem is intractable, simply because the feature queries might be too large. So, we explore a third problem: classifying new entities without necessarily generating the feature queries. Interestingly, in the case of bounded ghw we can efficiently classify without ever explicitly generating the feature queries.

An instance of the constraint satisfaction problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for a CSP is called robust if it outputs an assignment satisfying an $(1-g(\varepsilon))$-fraction of constraints on any $(1-\varepsilon)$-satisfiable instance, where the loss function $g$ is such that $g(\varepsilon)\rightarrow 0$ as $\varepsilon\rightarrow 0$. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some $g$) have been characterized by Barto and Kozik, with the general bound on the loss $g$ being doubly exponential, specifically $g(\varepsilon)=O((\log\log(1/\varepsilon))/\log(1/\varepsilon))$. It is natural to ask when a better loss can be achieved, in particular polynomial loss $g(\varepsilon)=O(\varepsilon^{1/k})$ for some constant $k$. In this paper, we consider CSPs with a constraint language having a near-unanimity polymorphism. This general condition almost matches a known necessary condition for having a robust algorithm with polynomial loss. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter $k$ in the loss depends on the size of the domain and the arity of the relations in $\Gamma$, while the other works for a special ternary near-unanimity operation called the dual discriminator with $k=2$ for any domain size. In the latter case, the CSP is a common generalization of Unique Games with a fixed domain and 2-Sat. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidefinite programming relaxation for the CSP.

An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for CSP is called robust if it outputs an assignment satisfying a (1 — g(∊))-fraction of constraints on any (1 — ∊)-satisfiable instance, where the loss function g is such that g(∊) → 0 as ∊ → 0. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some g) have been characterised by Barto and Kozik, with the general bound on the loss g being doubly exponential, specifically g(∊) = O((loglog(1/ ∊))/log(1/ ∊)). It is natural to ask when a better loss can be achieved: in particular, polynomial loss g(∊) = O(∊1/k) for some constant k. In this paper, we consider CSPs with a constraint language having a near- unanimity polymorphism. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter k in the loss depends on the size of the domain and the arity of the relations in Γ, while the other works for a special ternary near-unanimity operation called dual discriminator with k = 2 for any domain size. In the latter case, the CSP is a common generalisation of Unique Games with a fixed domain and 2-Sat. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidefinite programming relaxation for CSP.

Model checking---deciding if a logical sentence holds on a structure---is a basic computational task that is well known to be intractable in general. For first-order logic on finite structures, it is PSPACE-complete, and the natural evaluation algorithm exhibits exponential dependence on the formula. We study model checking on the quantified conjunctive fragment of first-order logic, namely, prenex sentences having a purely conjunctive quantifier-free part. Following a number of works, we associate a graph to the quantifier-free part; each sentence then induces a prefixed graph, a quantifier prefix paired with a graph on its variables. We give a comprehensive classification of the sets of prefixed graphs on which model checking is tractable based on a novel generalization of treewidth that generalizes and places into a unified framework a number of existing results.

The product homomorphism problem (PHP) takes as input a finite collection of structures A_1, ..., A_n and a structure B, and asks if there is a homomorphism from the direct product between A_1, A_2, ..., and A_n, to B. We pinpoint the computational complexity of this problem. Our motivation stems from the fact that PHP naturally arises in different areas of database theory. In particular, it is equivalent to the problem of determining whether a relation is definable by a conjunctive query, and the existence of a schema mapping that fits a given collection of positive and negative data examples. We apply our results to obtain complexity bounds for these problems.

The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been verified for conservative problems (also known as list homomorphism problems) by A. Bulatov (2003). Egri et al. (SODA 2014) augmented this result by showing that for digraph templates H, every conservative CSP, denoted LHOM(H), is solvable in log space or is hard for NL. A conjecture of Larose and Tesson from 2007 forecasts that when LHOM(H) is in log space, then in fact, it falls in a small subclass of log space, the set of problems expressible in symmetric Data log. The present work verifies the conjecture for LHOM(H) (and, indeed, for the wider class of conservative CSPs with binary constraints), and by so doing sharpens the aforementioned dichotomy. A combinatorial characterization of symmetric Data log provides the language in which the algorithmic ideas of the paper, quite different from the ones in Egri et al., are formalized.

We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language Γ on an arbitrary finite domain. The goal in such a problem is to minimize the number of unsatisfied constraints in a given instance of CSP(Γ). A recent result of Ene et al. says that, under the mild technical condition that Γ contains the equality relation, the basic LP relaxation is optimal for constant-factor approximation for Min CSP(Γ) unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we introduce a new natural algebraic condition, stable probability distributions on symmetric polymorphisms of a constraint language, and show that the presence of such distributions on polymorphisms of each arity is necessary and sufficient for the finiteness of the integrality gap for the basic LP relaxation of Min CSP(Γ). We also show how stable distributions on symmetric polymorphisms can in principle be used to round solutions of the basic LP relaxation, and how, for several examples that cover all previously known cases, this leads to efficient constant-factor approximation algorithms for Min CSP(Γ). Finally, we show that the absence of another condition, which is implied by stable distributions, leads to NP-hardness of constant-factor approximation.

Motivated by Fagin's characterization of NP, Saluja et al. have introduced a logic based frame- work for expressing counting problems. In this setting, a counting problem (seen as a mapping C from structures to non-negative integers) is `defined’ by a first-order sentence phi if for every instance A of the problem, the number of possible satisfying assignments of the variables of phi in A is equal to C(A). The logic RHPI_1 has been introduced by Dyer et al. in their study of the counting complexity class #BIS. The interest in the class #BIS stems from the fact that, it is quite plausible that the problems in #BIS are not #P-hard, nor they admit a fully polynomial randomized approximation scheme. In the present paper we investigate which counting constraint satisfaction problems #CSP(H) are definable in the monotone fragment of RHPI_1. We prove that #CSP(H) is definable in monotone RHPI_1 whenever H is invariant under meet and join operations of a distributive lattice. We prove that the converse also holds if H contains the equality relation. We also prove similar results for counting CSPs expressible by linear Datalog. The results in this case are very similar to those for monotone RHPI1, with the addition that H has, additionally, \top (the greatest element of the lattice) as a polymorphism.

A natural and established way to restrict the constraint satisfaction problem is to fix the relations that can be used to pose constraints; such a family of relations is called a constraint language.In this article, we study arc consistency, a heavily investigated inference method, and three extensions thereof from the perspective of constraint languages.We conduct a comparison of the studied methods on the basis of which constraint languages they solve, and we present new polynomial-time tractability results for singleton arc consistency, the most powerful method studied.

A schema mapping is a high-level specification of the relationship between a source schema and a target schema. Recently, a line of research has emerged that aims at deriving schema mappings automatically or semi-automatically with the help of data examples, that is, pairs consisting of a source instance and a target instance that depict, in some precise sense, the intended behavior of the schema mapping. Several different uses of data examples for deriving, refining, or illustrating a schema mapping have already been proposed and studied. In this article, we use the lens of computational learning theory to systematically investigate the problem of obtaining algorithmically a schema mapping from data examples. Our aim is to leverage the rich body of work on learning theory in order to develop a framework for exploring the power and the limitations of the various algorithmic methods for obtaining schema mappings from data examples. We focus on GAV schema mappings, that is, schema mappings specified by GAV (Global-As-View) constraints. GAV constraints are the most basic and the most widely supported language for specifying schema mappings. We present an efficient algorithm for learning GAV schema mappings using Angluin's model of exact learning with membership and equivalence queries. This is optimal, since we show that neither membership queries nor equivalence queries suffice, unless the source schema consists of unary relations only. We also obtain results concerning the learnability of schema mappings in the context of Valiant's well-known PAC (Probably-Approximately-Correct) learning model, and concerning the learnability of restricted classes of GAV schema mappings. Finally, as a byproduct of our work, we show that there is no efficient algorithm for approximating the shortest GAV schema mapping fitting a given set of examples, unless the source schema consists of unary relations only.

A schema mapping is a high-level specification of the relationship between a source schema and a target schema. Recently, a line of research has emerged that aims at deriving schema mappings automatically or semi-automatically with the help of data examples, i.e., pairs consisting of a source instance and a target instance that depict, in some precise sense, the intended behavior of the schema mapping. Several different uses of data examples for deriving, refining, or illustrating a schema mapping have already been proposed and studied.

Model checking-deciding if a logical sentence holds on a structure-is a basic computational task that is well-known to be intractable in general. For first-order logic on finite structures, it is PSPACE-complete, and the natural evaluation algorithm exhibits exponential dependence on the formula. We study model checking on the quantified conjunctive fragment of first-order logic, namely, prenex sentences having a purely conjunctive quantifier-free part. Following a number of works, we associate a graph to the quantifier-free part; each sentence then induces a prefixed graph, a quantifier prefix paired with a graph on its variables. We give a comprehensive classification of the sets of prefixed graphs on which model checking is tractable, based on a novel generalization of treewidth, that generalizes and places into a unified framework a number of existing results.

The homomorphism problem for relational structures is an abstract way of formulating constraint satisfaction problems (CSP) and various problems in database theory. The decision version of the homomorphism problem received a lot of attention in literature; in particular, the way the graph-theoretical structure of the variables and constraints influences the complexity of the problem is intensively studied. Here we study the problem of enumerating all the solutions with polynomial delay from a similar point of view. It turns out that the enumeration problem behaves very differently from the decision version. We give evidence that it is unlikely that a characterization result similar to the decision version can be obtained. Nevertheless, we show nontrivial cases where enumeration can be done with polynomial delay.

The study of constraint satisfaction problems definable in various fragments of Datalog has recently gained considerable importance. We consider constraint satisfaction problems that are definable in the smallest natural recursive fragment of Datalog- monadic linear Datalog with at most one EDB per rule, and also in the smallest non-linear extension of this fragment. We give combinatorial and algebraic characterisations of such problems, in terms of homomorphism dualities and lattice operations, respectively. We then apply our results to study graph H-colouring problems. 1

The study of constraint satisfaction problems definable in various fragments of Datalog has recently gained considerable importance. We consider constraint satisfaction problems that are definable in the smallest natural recursive fragment of Datalog - monadic linear Datalog with at most one EDB per rule. We give combinatorial and algebraic characterisations of such problems, in terms of caterpillar dualities and lattice operations, respectively. We then apply our results to study graph H-colouring problems.

Let B be a finite, core relational structure and let A be the algebra associated to B, i.e. whose terms are the operations on the universe of B that preserve the relations of B. We show that if A generates a so-called arithmetical variety then CSP(B), the constraint satisfaction problem associated to B, is solvable in Logspace; in fact notCSP(B) is expressible in symmetric Datalog. In particular, we obtain that notCSP(B) is expressible in Datalog and the relations of B are invariant under a Maltsev operation then notCSP(B) is in symmetric Datalog.

A retraction from a structure P to its substructure Q is a homomorphism from P onto Q that is the identity on Q. We present an algebraic condition which completely characterzies all posets and all reflexive graphs Q such that the class of all posets or reflexive graphs, respectively, that admit a retraction onto Q is first-order definable.

Generalized majority-minority (GMM) operations are introduced as a common generalization of near unanimity operations and Mal'tsev operations on finite sets. We show that every instance of the constraint satisfaction problem (CSP), where all constraint relations are invariant under a (fixed) GMM operation, is solvable in polynomial time. This constitutes one of the largest tractable cases of the CSP.

A Mal'tsev operation is a ternary operation $\varphi$ that satisfies the identities $\varphi(x,y,y) = \varphi(y,y,x) = x$. Constraint satisfaction problems involving constraints invariant under a Mal'tsev operation constitute an important class of constraint satisfaction problems, which includes the affine satisfiability problem, subgroupand near subgroup constraints, and many others. It is also known that any tractable case of the counting constraint satisfaction problem involves only Mal'tsev constraints. The first algorithm solving the arbitrary constraint satisfaction problem with Mal'tsev constraints has been given by Bulatov. However, this algorithm is very sophisticated and relies heavily on advanced algebraic machinery. In this paper, we give a different and much simpler algorithm for this type of constraint.

Let A be a finite set and let /spl phi/ : A/sup k//spl rarr/A with k/spl ges/3 be a k-ary operation on A. We say that /spl phi/ is a generalized majority-minority (GMM) operation if for all a, b /spl isin/ A we have that /spl phi/(x, y,...,y) = /spl phi/(y, x,..,y) =...=/spl phi/(y, y,..,x) = y for all x, y /spl isin/ {a, b} or /spl phi/{x, y,..,y) = /spl phi/(y, y,..,x) = x for all x, y /spl isin/ {a, b}. Near-unanimity and Mal'tsev operations are particular instances of GMM operations. We prove that every CSP instance where all constraint relations are invariant under a (fixed) GMM operation is solvable in polynomial time. This constitutes one of the largest tractable cases of the CSP.

In this paper we systematically investigate the connections between logics with a finite number of variables, structures of bounded pathwidth, and linear Datalog Programs. We prove that, in the context of Constraint Satisfaction Problems, all these concepts correspond to different mathematical embodiments of a unique robust notion that we call bounded path duality. We also study the computational complexity implications of the notion of bounded path duality. We show that every constraint satisfaction problem $\csp(\best)$ with bounded path duality is solvable in NL and that this notion explains in a uniform way all families of CSPs known to be in NL. Finally, we use the results developed in the paper to identify new problems in NL.

A retraction from a structure P to its substructure Q is a homomorphism from P onto Q that is the identity on Q. We present an algebraic condition which completely characterises all posets and all reflexive graphs Q with the following property: the class of all posets or reflexive graphs, respectively, that admit a retraction onto Q is first-order definable.

The Counting Constraint Satisfaction Problem (#CSP) over a finite domain can be expressed as follows: given a first-order formula consisting of a conjunction of predicates, determine the number of satisfying assignments to the formula. #CSP can be parametrized by the set of allowed constraint predicates. In this paper we start a systematic study of subclasses of #CSP restricted in this way. The ultimate goal of this investigation is to distinguish those restricted subclasses of #CSP which are tractable, i.e. solvable in polynomial time, from those which are not. We show that the complexity of any restricted #CSP class on a finite domain can be deduced from the properties of polymorphisms of the allowed constraints, similar to that for the decision CSP. Then we prove that if a subclass of the #CSP is tractable, then constraints allowed by the class satisfy some very restrictive condition: it has to have a Mal'tsev polymorphism, that is a ternary operation m(x, y, z) such that m(x, y, y) = m(y, y, x) = x. This condition uniformly explains all existing complexity results for particular cases of #CSP, and allows us to obtain new results and to conjecture a criterion distinguishing tractable counting CSPs. We also obtain a dichotomy theorem for the complexity of #CSP with a 3-element domain and give new simpler proofs of the dichotomy results for the problem of counting graph homomorphisms.

We consider the following classes of quantified boolean formulas. Fix a finite set of basic boolean functions. Take conjunctions of these basic functions applied to variables and constants in arbitrary way. Finally quantify existentially or universally some of the variables. We prove the following dichotomy theorem: For any set of basic boolean functions, the resulting set of formulas is either polynomially learnable from equivalence queries alone or else it is not PAC-predictable even with membership queries under cryptographic assumptions. Furthermore we identify precisely which sets of basic functions are in which of the two cases. Work supported in part by the Spanish Government through grant AP94 43716784 and the DGICYT (project BP92-0709) and the EC through the Esprit BRA Program (Working Group 8556, NeuroColt and project 20244, ALCOM IT). 1 Introduction The problem of learning an unknown boolean formula under some determined protocol has been widely studied. It is well know...