Open this publication in new window or tab >>2021 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 296, article id 103505Article in journal (Refereed) Published
Abstract [en]
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.
Place, publisher, year, edition, pages
Elsevier, 2021
Keywords
Constraint satisfaction problems, Infinite domains, Partition schemes, Lower bounds
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-175145 (URN)10.1016/j.artint.2021.103505 (DOI)000648650600003 ()
Note
Funding: Wallenberg AI, Autonomous Systems and Software Program (WASP) - Knut and Alice Wallenberg Foundation; Swedish Research Council (VR)Swedish Research Council [2017-04112]; VRSwedish Research Council [2019-03690]
2021-04-202021-04-202021-06-01Bibliographically approved