Counting the number of answers to conjunctive queries is a fundamental problem in databases that, under standard assumptions, does not have an efficient solution. The issue is inherently #P-hard, extending even to classes of acyclic instances. To address this, we pinpoint tractable classes by examining the structural properties of instances and introducing the novel concept of #-hypertree decomposition. We establish the feasibility of counting answers in polynomial time for classes of queries featuring bounded #-hypertree width. Additionally, employing novel techniques from the realm of fixed-parameter computational complexity, we prove that, for bounded arity queries, the bounded #-hypertree width property precisely delineates the frontier of tractability for the counting problem. This result closes an important gap in our understanding of the complexity of such a basic problem for conjunctive queries and, equivalently, for constraint satisfaction problems (CSPs). Drawing upon #-hypertree decompositions, a ''hybrid'' decomposition method emerges. This approach leverages both the structural characteristics of the query and properties intrinsic to the input database, including keys or other (weaker) degree constraints that limit the permissible combinations of values. Intuitively, these features may introduce distinct structural properties that elude identification through the ''worst-possible database'' perspective inherent in purely structural methods.

The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variables satisfying all of the constraints. One formulation of the CSP is as the problem of deciding, given a pair (G,H) of relational structures, whether or not there is a homomorphism from the first structure to the second structure. The CSP is in general NP-hard; a common way to restrict this problem is to fix the second structure H, so that each structure H gives rise to a problem CSP(H). The problem family CSP(H) has been studied using an algebraic approach, which links the algorithmic and complexity properties of each problem CSP(H) to a set of operations, the so-called polymorphisms of H. Certain types of polymorphisms are known to imply the polynomial-time tractability of $CSP(H)$, and others are conjectured to do so. This article systematically studies---for various classes of polymorphisms---the computational complexity of deciding whether or not a given structure H admits a polymorphism from the class. Among other results, we prove the NP-completeness of deciding a condition conjectured to characterize the tractable problems CSP(H), as well as the NP-completeness of deciding if CSP(H) has bounded width.

We consider the quantified constraint satisfaction problem (QCSP) which is to decide, given a structure and a first-order sentence (not assumed here to be in prenex form) built from conjunction and quantification, whether or not the sentence is true on the structure. We present a proof system for certifying the falsity of QCSP instances and develop its basic theory; for instance, we provide an algorithmic interpretation of its behavior. Our proof system places the established Q-resolution proof system in a broader context, and also allows us to derive QCSP tractability results.

The constraint satisfaction problem (CSP) on a relational structure B is to decide, given a set of constraints on variables where the relations come from B, whether or not there is a assignment to the variables satisfying all of the constraints; the surjective CSP is the variant where one decides the existence of a surjective satisfying assignment onto the universe of B. We present an algebraic condition on the polymorphism clone of B and prove that it is sufficient for the hardness of the surjective CSP on a finite structure B, in the sense that this problem admits a reduction from a certain fixed-structure CSP. To our knowledge, this is the first result that allows one to use algebraic information from a relational structure B to infer information on the complexity hardness of surjective constraint satisfaction on B. A corollary of our result is that, on any finite non-trivial structure having only essentially unary polymorphisms, surjective constraint satisfaction is NP-complete.

We present a domain-independent algorithm that computes macros in a novel way. Our algorithm computes macros "on-the-fly" for a given set of states and does not require previously learned or inferred information, nor prior domain knowledge. The algorithm is used to define new domain-independent tractable classes of classical planning that are proved to include \emph{Blocksworld-arm} and \emph{Towers of Hanoi}.

This paper studies peek arc consistency, a reasoning technique that extends the well-known arc consistency technique for constraint satisfaction. In contrast to other more costly extensions of arc consistency that have been studied in the literature, peek arc consistency requires only linear space and quadratic time and can be parallelized in a straightforward way such that it runs in linear time with a linear number of processors. We demonstrate that for various constraint languages, peek arc consistency gives a polynomial-time decision procedure for the constraint satisfaction problem. We also present an algebraic characterization of those constraint languages that can be solved by peek arc consistency, and study the robustness of the algorithm.

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.