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.

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 such that a CSP over an arbitrary finite equality language is solvable in O(cn) time (n is the number of variables). Stronger lower bounds are possible for infinite equality languages where we rule out the existence of 2o(nlog⁡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(cn) 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(cn) 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.

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.

Qualitative reasoning is an important subfeld ofartifcial intelligence where one describes relationships with qualitative, rather than numerical, relations. Many such reasoning tasks, e.g., ALLEN’SINTERVAL 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 coarsegrained 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)ⁿ,time, and prove several fundamental properties ofthese classes. We proceed by studying temporal reasoning problems and (1) show that the PARTIALLYORDERED 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 intervaloverlapping with more than k others is solvable in (2nk)^2k· 2ⁿ time and is included in FPE. Our multivariate approach is in no way limited to these tospecifc problems and may be a generally useful approach for obtaining single-exponential algorithms. 

Strong partial clones are composition closed sets of partial operations containing all partial projections, characterizable as partial polymorphisms of sets of relations Γ (pPol(Γ)). If C is a clone it is known that the set of all strong partial clones whose total component equals C, has a greatest element pPol(Γω), where Γω is called a weak base. Weak bases have seen applications in computer science due to their usefulness for proving complexity classifications for constraint satisfaction related problems. In this article we (1) completely describe the inclusion structure between pPol(Γω), pPol(Δω) for all Boolean weak bases Γω and Δω and (2) in many such cases prove that the strong partial clones in question uniquely cover each other.

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.

The inverse satisfiability problem over a set of relations Gamma (INv-SAT(Gamma)) is the problem of deciding whether a relation R can be defined as the set of models of a SAT(Gamma) instance. Kavvadias and Sideri (1998) [15] obtained a dichotomy between P and co-NP-complete for finite r containing the two constant Boolean relations. However, for arbitrary constraint languages the complexity has been wide open, and in this article we finally prove a complete dichotomy theorem for finite languages. Kavvadias and Sideris techniques are not applicable and we have to turn to the more recent algebraic approach based on partial polymorphisms. We also study the complexity of the inverse constraint satisfaction problem prove a general hardness result, which in particular resolves the complexity of INvERSE k-COLOURING, mentioned as an open problem in Chen (2008) [8]. (C) 2020 Elsevier Inc. All rights reserved.

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.

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. 

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(cn) time (n is the number of variables). Stronger lower bounds are possible for infinite equality languages where we rule out the existence of 2o(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(cn) 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(cn) time for a fixed c. © 2020 Inst. Sci. inf., Univ. Defence in Belgrade. All rights reserved.