The region connection calculus (RCC) and Allen's interval algebra (IA) are two well-known NP-hard spatial-temporal qualitative reasoning problems. They are solvable in 2^(O(n log n)) time, where n is the number of variables, and IA is additionally known to be solvable in o(n)^n time. However, no improvement over exhaustive search is known for RCC, and if they are also solvable in single exponential time 2^O(n) is unknown. We investigate multiple avenues towards reaching such bounds. First, we show that branching is insufficient since there are too many non-redundant constraints. Concretely, we classify the maximum number of non-redundant constraints in RCC and IA. Algorithmically, we make two significant contributions based on dynamic programming (DP). The first algorithm runs in 4^n time and is applicable to a non-trivial, NP-hard fragment of IA, which includes the well-known interval graph sandwich problem of (Golumbic and Shamir 1993). For the richer RCC problem with 8 basic relations we use a more sophisticated approach which asymptotically matches the o(n)^n bound for IA.

Determining the validity of a quantified Boolean formula (QBF) is a PSPACE-complete problem with rich expressive power. Despite interest in efficient solvers, there is, compared to problems in NP, a lack of positive theoretical results, and in the parameterized complexity setting one often has to restrict the quantifier prefix (e.g., bounding alternations) to obtain fixed parameter tractability (FPT). We propose a new parameter: the number of variables in clauses that has to be removed before reaching a tractable class (a clause covering (CC) backdoor). We are then interested in solving QBF in FPT time given a CC-backdoor of size k. We consider the three classical, tractable cases of QBF as base classes: Horn, 2-CNF, and linear equations. We establish W[1]-hardness for Horn but prove FPT for the others, and prove that in a precise, algebraic sense, we are only missing one important case for a full dichotomy. Our algorithms are non-trivial and depend on propagation, and Gaussian elimination, respectively, and are comparably unexplored for QBF.

International audience

Abstract The H - Coloring problem is a well-known generalization of the classical -complete problem k - Coloring where the task is to determine whether an input graph admits a homomorphism to the template graph H . This problem has been the subject of intense theoretical research and in this article we study the complexity of H - Coloring with respect to the parameters clique-width and the more recent component twin-width , which describe desirable computational properties of graphs. We give two surprising linear bounds between these parameters, thus improving the previously known exponential and double exponential bounds. Our constructive proof naturally extends to related parameters and as a showcase we prove that total twin-width and linear clique-width can be related via a tight quadratic bound. These bounds naturally lead to algorithmic applications. The linear bounds between component twin-width and clique-width entail natural approximations of component twin-width, by making use of the results known for clique-width. As for computational aspects of graph coloring, we target the richer problem of counting the number of homomorphisms to H (# H - Coloring ). The first algorithm that we propose uses a contraction sequence of the input graph G parameterized by the component twin-width of G . This leads to a positive result for the counting version. The second uses a contraction sequence of the template graph H and here we instead measure the complexity with respect to the number of vertices in the input graph. Using our linear bounds we show that our algorithms are always at least as fast as the previously best # H -Coloring algorithms (based on clique-width) and for several interesting classes of graphs (e.g., cographs, cycles of length $$\varvec{\ge 7}$$ ≥ 7 , or distance-hereditary graphs) are in fact strictly faster.

Argumentation is a central subarea of Artificial Intelligence (AI) for modeling and reasoning about arguments. The semantics of abstract argumentation frameworks (AFs) is given by sets of arguments (extensions) and conditions on the relationship between arguments, such as stable or admissible. Today's solvers implement tasks such as finding extensions, deciding credulously or skeptically acceptance, counting, or enumerating extensions. While these tasks are well charted, the area between decision and counting/enumeration and fine-grained reasoning requires expensive reasoning so far. We introduce a novel concept (facets) for reasoning between decision and enumeration. Facets are arguments that belong to some extensions (credulous) but not to all extensions (skeptical). They are most natural when a user aims to navigate, filter, or comprehend specific arguments, according to their needs. We study the complexity and show that tasks involving facets are much easier than counting extensions. Finally, we provide an implementation, and conduct experiments to demonstrate feasibility.

The Boolean satisfiability problem (SAT) is a well-known example of monotonic reasoning, of intense practical interest due to fast solvers, complemented by rigorous fine-grained complexity results. However, for non-monotonic reasoning, e.g., abductive reasoning, comparably little is known outside classic complexity theory. In this paper we take a first step of bridging the gap between monotonic and non-monotonic reasoning by analyzing the complexity of intractable abduction problems under the seemingly overlooked but natural parameter n: the number of variables in the knowledge base. We obtain several positive results for SigmaP2- as well as NP- and coNP-complete fragments, which implies the first example of beating exhaustive search for a SigmaP2-complete problem (to the best of our knowledge). We complement this with lower bounds and for many fragments rule out improvements under the (strong) exponential-time hypothesis.

Abstract Abductive reasoning is a popular non-monotonic paradigm that aims to explain observed symptoms and manifestations. It has many applications, such as diagnosis and planning in artificial intelligence and database updates. In propositional abduction, we focus on specifying knowledge by a propositional formula. The computational complexity of tasks in propositional abduction has been systematically characterized – even with detailed classifications for Boolean fragments. Unsurprisingly, the most insightful reasoning problems (counting and enumeration) are computationally highly challenging. Therefore, we consider reasoning between decisions and counting, allowing us to understand explanations better while maintaining favorable complexity. We introduce facets to propositional abductions, which are literals that occur in some explanation (relevant) but not all explanations (dispensable). Reasoning with facets provides a more fine-grained understanding of variability in explanations (heterogeneous). In addition, we consider the distance between two explanations, enabling a better understanding of heterogeneity/homogeneity. We comprehensively analyze facets of propositional abduction in various settings, including an almost complete characterization in Post’s framework.

Partially ordered models of time occur naturally in applications where agents/processes cannot perfectly communicate with each other, and can be traced back to the seminal work of Lamport. In this paper we consider the problem of deciding if a (likely incomplete) description of a system of events is consistent, the network consistency problem for the point algebra of partially ordered time (POT). While the classical complexity of this problem has been fully settled, comparably little is known of the fine-grained complexity of POT except that it can be solved in O*((0.368n)^n) time by enumerating ordered partitions. We construct a much faster algorithm with a run-time bounded by O*((0.26n)^n), which, e.g., is roughly 1000 times faster than the naive enumeration algorithm in a problem with 20 events. This is achieved by a sophisticated enumeration of structures similar to total orders, which are then greedily expanded toward a solution. While similar ideas have been explored earlier for related problems it turns out that the analysis for POT is non-trivial and requires significant new ideas.

Allen's interval algebra is one of the most well-known calculi in qualitative temporal reasoning with numerous applications in artificial intelligence. Very recently, there has been a surge of improvements in the fine-grained complexity of NP-hard reasoning tasks in this algebra, which has improved the running time from the naive 2^O(n^2) to O*((1.0615n)^n), and even faster algorithms are known for unit intervals and the case when we a bounded number of overlapping intervals. Despite these improvements the best known lower bound is still only 2^o(n) under the exponential-time hypothesis and major improvements in either direction seemingly require fundamental advances in computational complexity. In this paper we propose a novel framework for solving NP-hard qualitative reasoning problems which we refer to as dynamic programming with sublinear partitioning. Using this technique we obtain a major improvement of O*((cn/log(n))^n) for Allen's interval algebra. To demonstrate that the technique is applicable to further problem domains we apply it to a problem in qualitative spatial reasoning, the cardinal direction calculus, and solve it in O*((cn/log(n))^(2n/3)) time. Hence, not only do we significantly advance the state-of-the-art for NP-hard qualitative reasoning problems, but obtain a novel algorithmic technique that is likely applicable to many problems where 2^O(n) time algorithms are unlikely.

Abstract We study the fine-grained complexity of NP-complete, infinite-domain constraint satisfaction problems (CSPs) parameterised by a set of first-order definable relations (with equality). Such CSPs are of central importance since they form a subclass of any infinite-domain CSP parameterised by a set of first-order definable relations over a relational structure (possibly containing more than just equality). We prove that under the randomised exponential-time hypothesis it is not possible to find $$c > 1$$ c > 1 such that a CSP over an arbitrary finite equality language is solvable in $$O(c^n)$$ O ( c n ) time (n is the number of variables). Stronger lower bounds are possible for infinite equality languages where we rule out the existence of $$2^{o(n \log n)}$$ 2 o ( n log n ) time algorithms; a lower bound which also extends to satisfiability modulo theories solving for an arbitrary background theory. Despite these lower bounds we prove that for each $$c > 1$$ c > 1 there exists an NP-hard equality CSP solvable in $$O(c^n)$$ O ( c n ) time. Lower bounds like these immediately ask for closely matching upper bounds, and we prove that a CSP over a finite equality language is always solvable in $$O(c^n)$$ O ( c n ) time for a fixed c, and manage to extend this algorithm to the much broader class of CSPs where constraints are formed by first-order formulas over a unary structure.

Qualitative reasoning is an important subfield of artificial intelligence where one describes relationships with qualitative, rather than numerical, relations. Many such reasoning tasks, e.g., Allen's interval algebra, can be solved in 2^O(n*log n) time, but single-exponential running times 2^O(n) are currently far out of reach. In this paper we consider single-exponential algorithms via a multivariate analysis consisting of a fine-grained parameter n (e.g., the number of variables) and a coarse-grained parameter k expected to be relatively small. We introduce the classes FPE and XE of problems solvable in f(k)*2^O(n), respectively f(k)^n, time, and prove several fundamental properties of these classes. We proceed by studying temporal reasoning problems and (1) show that the partially ordered time problem of effective width k is solvable in 16^{kn} time and is thus included in XE, and (2) that the network consistency problem for Allen's interval algebra with no interval overlapping with more than k others is solvable in (2nk)^{2k}*2^n time and is included in FPE. Our multivariate approach is in no way limited to these to specific problems and may be a generally useful approach for obtaining single-exponential algorithms.

A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found many applications in artificial intelligence and elsewhere, and the algorithmic problem of finding such backdoors has consequently been intensively studied. Sioutis and Janhunen have proposed a generalised backdoor concept suitable for infinite-domain CSP instances over binary constraints. We generalise their concept into a large class of CSPs that allow for higher-arity constraints. We show that this kind of infinite-domain backdoors have many of the positive computational properties that finite-domain backdoors have: the associated computational problems are fixed parameter tractable whenever the underlying constraint language is finite. On the other hand, we show that infinite languages make the problems considerably harder: the general backdoor detection problem is W[2]-hard and fixed-parameter tractability is ruled out under standard complexity-theoretic assumptions. We demonstrate that backdoors may have suboptimal behaviour on binary constraints—this is detrimental from an AI perspective where binary constraints are predominant in, for instance, spatiotemporal applications. In response to this, we introduce sidedoors as an alternative to backdoors. The fundamental computational problems for sidedoors remain fixed-parameter tractable for finite constraint language (possibly also containing non-binary relations). Moreover, the sidedoor approach has appealing computational properties that sometimes leads to faster algorithms than the backdoor approach.

A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found many applications in artificial intelligence and elsewhere, and the algorithmic problem of finding such backdoors has consequently been intensively studied. Sioutis and Janhunen (KI, 2019) have proposed a generalised backdoor concept suitable for infinite-domain CSP instances over binary constraints. We generalise their concept into a large class of CSPs that allow for higher-arity constraints. We show that this kind of infinite-domain backdoors have many of the positive computational properties that finite-domain backdoors have: the associated computational problems are fixed-parameter tractable whenever the underlying constraint language is finite. On the other hand, we show that infinite languages make the problems considerably harder.

The constraint satisfaction problem (CSP) is an important framework in artificial intelligence used to model e.g. qualitative reasoning problems such as Allen's interval algebra A. There is strong practical incitement to solve CSPs as efficiently as possible, and the classical complexity of temporal CSPs, including A, is well understood. However, the situation is more dire with respect to running time bounds of the form O(f(n)) (where n is the number of variables) where existing results gives a best theoretical upper bound 2^O(n * log n) which leaves a significant gap to the best (conditional) lower bound 2^o(n). In this paper we narrow this gap by presenting two novel algorithms for temporal CSPs based on dynamic programming. The first algorithm solves temporal CSPs limited to constraints of arity three in O(3^n) time, and we use this algorithm to solve A in O((1.5922n)^n) time. The second algorithm tackles A directly and solves it in O((1.0615n)^n), implying a remarkable improvement over existing methods since no previously published algorithm belongs to O((cn)^n) for any c. We also extend the latter algorithm to higher dimensions box algebras where we obtain the first explicit upper bound.

Many computational problems arising in, for instance, artificial intelligence can be realized as infinite-domain constraint satisfaction problems (CSPs) based on partition schemes: a set of pairwise disjoint binary relations (containing the equality relation) whose union spans the underlying domain and which is closed under converse. We first consider partition schemes that contain an acyclic order and where the constraint language contains all unions of the basic relations; such CSPs are frequently occurring in e.g. temporal and spatial reasoning. We identify properties of such orders which, when combined, are sufficient to establish NP-hardness of the CSP and strong lower bounds under the exponential-time hypothesis, even for degree-bounded problems. This result explains, in a uniform way, many existing hardness results from the literature, and shows that it is impossible to obtain subexponential time algorithms unless the exponential-time hypothesis fails. However, some of these problems (including several important temporal problems), despite likely not being solvable in subexponential time, admit non-trivial improved exponential-time algorithm, and we present a novel improved algorithm for RCC-8 and related formalisms.

Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Algebraic techniques introduced by Jonsson et al. (2017) [4] show that the fine-grained time complexity of the parameterized problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation R such that can be solved at least as fast as any other NP-hard problem. In this paper we extend this method and show that such languages also exist for the surjective SAT problem, the max ones problem, the propositional abduction problem, and the Boolean valued constraint satisfaction problem over finite-valued constraint languages. These languages may be interesting when investigating the borderline between polynomial time, subexponential time and exponential-time algorithms since they in a precise sense can be regarded as NP-hard problems with minimum time complexity. Indeed, with the help of these languages we relate all of the above problems to the exponential time hypothesis (ETH) in several different ways.

We study the fine-grained complexity of NP-complete, infinite-domain constraint satisfaction problems (CSPs) parameterised by a set of first-order definable relations (with equality). Such CSPs are of central importance since they form a subclass of any infinite-domain CSP parameterised by a set of first-order definable relations. We prove that under the randomised exponential-time hypothesis it is not possible to find c > 1 such that a CSP over an arbitrary finite equality language is solvable in O(c^n) time (n is the number of variables). Stronger lower bounds are possible for infinite equality languages where we rule out the existence of 2^o(n log n) time algorithms; a lower bound which also extends to satisfiability modulo theories solving for an arbitrary background theory. Despite these lower bounds we prove that for each c > 1 there exists an NP-hard equality CSP solvable in O(c^n) time. Lower bounds like these immediately ask for closely matching upper bounds, and we prove that a CSP over a finite equality language is always solvable in O(c^n) time for a fixed c.

Uniqueness quantification (Exists!) is a quantifier in first-order logic where one requires that exactly one element exists satisfying a given property. In this paper we investigate the strength of uniqueness quantification when it is used in place of existential quantification in conjunctive formulas over a given set of relations Gamma, so-called primitive positive definitions (pp-definitions). We fully classify the Boolean sets of relations where uniqueness quantification has the same strength as existential quantification in pp-definitions and give several results valid for arbitrary finite domains. We also consider applications of Exists!-quantified pp-definitions in computer science, which can be used to study the computational complexity of problems where the number of solutions is important. Using our classification we give a new and simplified proof of the trichotomy theorem for the unique satisfiability problem, and prove a general result for the unique constraint satisfaction problem. Studying these problems in a more rigorous framework also turns out to be advantageous in the context of lower bounds, and we relate the complexity of these problems to the exponential-time hypothesis.

Many computational problems arising in, for instance, artificial intelligence can be realized as infinite-domain constraint satisfaction problems (CSPs) based on partition schemes: a set of pairwise disjoint binary relations (containing the equality relation) whose union spans the underlying domain and which is closed under converse. We first consider partition schemes that contain a strict partial order and where the constraint language contains all unions of the basic relations; such CSPs are frequently occurring in e.g. temporal and spatial reasoning. We identify three properties of such orders which, when combined, are sufficient to establish NP-hardness of the CSP. This result explains, in a uniform way, many existing hardness results from the literature. More importantly, this result enables us to prove that CSPs of this kind are not solvable in subexponential time unless the exponential-time hypothesis (ETH) fails. We continue by studying constraint languages based on partition schemes but where relations are built using disjunctions instead of unions; such CSPs appear naturally when analysing first-order definable constraint languages. We prove that such CSPs are NP-hard even in very restricted settings and that they are not solvable in subexponential time under the randomised ETH. In certain cases, we can additionally show that they cannot be solved in O(c^n) time for any c >= 0.

The inverse satisfiability problem over a set of Boolean relations Gamma (Inv-SAT(Gamma)) is the computational decision problem of, given a set of models R, deciding whether there exists a SAT(Gamma) instance with R as its set of models. This problem is co-NP-complete in general and a dichotomy theorem for finite Γ containing the constant Boolean relations was obtained by Kavvadias and Sideri. In this paper we remove the latter condition and prove that Inv-SAT(Gamma) is always either tractable or co-NP-complete for all finite sets of relations Gamma, thus solving a problem open since 1998. Very little of the techniques used by Kavvadias and Sideri are applicable and we have to turn to more recently developed algebraic approaches based on partial polymorphisms. We also consider the case when Γ is infinite, where the situation differs markedly from the case of SAT. More precisely, we show that there exists infinite Gamma such that Inv-SAT(Gamma) is tractable even though there exists finite Delta is subset of Gamma such that Inv-SAT(Delta) is co-NP-complete.

Two well-studied closure operators for relations are based on existentially quantified conjunctive formulas, primitive positive (p.p.) definitions, and primitive positive formulas without existential quantification, quantifier-free primitive positive definitions (q.f.p.p.) definitions. Sets of relations closed under p.p. definitions are known as co-clones and sets of relations closed under q.f.p.p. definitions as weak partial co-clones. The latter do however have limited expressivity, and the corresponding lattice of strong partial clones is of uncountably infinite cardinality even for the Boolean domain. Hence, it is reasonable to consider the expressiveness of p.p. definitions where only a small number of existentially quantified variables are allowed. In this article, we consider p.p. definitions allowing only polynomially many existentially quantified variables, and say that a co-clone closed under such definitions is polynomially closed, and otherwise superpolynomially closed. We investigate properties of polynomially closed co-clones and prove that if the corresponding clone contains a k-ary near-unanimity operation for k≥3⁠, then the co-clone is polynomially closed, and if the clone does not contain a k-edge operation for any k≥2⁠, then the co-clone is superpolynomially closed. For the Boolean domain we strengthen these results and prove a complete dichotomy theorem separating polynomially closed co-clones from superpolynomially closed co-clones. Using these results, we then proceed to investigate properties of strong partial clones corresponding to superpolynomially closed co-clones. We prove that if Γ is a finite set of relations over an arbitrary finite domain such that the clone corresponding to Γ is essentially unary, then the strong partial clone corresponding to Γ is of infinite order and cannot be generated by a finite set of partial functions.

The parameterized satisfiability problem over a set of Boolean relations Gamma (SAT(Gamma)) is the problem of determining whether a conjunctive formula over Gamma has at least one model. Due to Schaefer's dichotomy theorem the computational complexity of SAT(Gamma), modulo polynomial-time reductions, has been completely determined: SAT(Gamma) is always either tractable or NP-complete. More recently, the problem of studying the relationship between the complexity of the NP-complete cases of SAT(Gamma) with restricted notions of reductions has attracted attention. For example, Impagliazzo et al. studied the complexity of k-SAT and proved that the worst-case time complexity increases infinitely often for larger values of k, unless 3-SAT is solvable in subexponential time. In a similar line of research Jonsson et al. studied the complexity of SAT(Gamma) with algebraic tools borrowed from clone theory and proved that there exists an NP-complete problem SAT(R^{neq,neq,neq,01}_{1/3}) such that there cannot exist any NP-complete SAT(Gamma) problem with strictly lower worst-case time complexity: the easiest NP-complete SAT(Gamma) problem. In this paper we are interested in classifying the NP-complete SAT(Gamma) problems whose worst-case time complexity is lower than 1-in-3-SAT but higher than the easiest problem SAT(R^{neq,neq,neq,01}_{1/3}). Recently it was conjectured that there only exists three satisfiability problems of this form. We prove that this conjecture does not hold and that there is an infinite number of such SAT(Gamma) problems. In the process we determine several algebraic properties of 1-in-3-SAT and related problems, which could be of independent interest for constructing exponential-time algorithms.

The construction of exact exponential-time algorithms for NP-complete problems has for some time been a very active research area. Unfortunately, there is a lack of general methods for studying and comparing the time complexity of algorithms for such problems. We propose such a method based on clone theory and demonstrate it on the SAT problem. Schaefer has completely classified the complexity of SAT with respect to the set of allowed relations and proved that this parameterized problem exhibits a dichotomy: it is either in P or is NP-complete. We show that there is a certain partial order on the NP-complete SAT problems with a close connection to their worst-case time complexities; if a problem SAT(S) is below a problem SAT(S′) in this partial order, then SAT(S′) cannot be solved strictly faster than SAT(S). By using this order, we identify a relation R such that SAT({R}) is the computationally easiest NP-complete SAT(S) problem. This result may be interesting when investigating the borderline between P and NP since one appealing way of studying this borderline is to identify problems that, in some sense, are situated close to it (such as a ‘very hard’ problem in P or a ‘very easy’ NP-complete problem). We strengthen the result by showing that SAT({R})-2 (i.e. SAT({R}) restricted to instances where no variable appears more than twice) is NP-complete, too. This is in contrast to, for example, l-in-3-SAT (or even CNF-SAT), which is in P under the same restriction. We then relate SAT({R})-2 to the exponential-time hypothesis (ETH) and show that ETH holds if and only if SAT({R})-2 is not sub-exponential. This constitutes a strong connection between ETH and the SAT problem under both severe relational and severe structural restrictions, and it may thus serve as a tool for studying the borderline between sub-exponential and exponential problems. In the process, we also prove a stronger version of Impagliazzo et al.'s sparsification lemma for k-SAT; namely that all finite Boolean constraint languages S and S′ such that SAT(·) is NP-complete can be sparsified into each other. This should be compared with Santhanam and Srinivasan's recent negative result which states that the same does not hold for all infinite Boolean constraint languages.