Öppna denna publikation i ny flik eller fönster >>2021 (Engelska)Ingår i: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 296, artikel-id 103505Artikel i tidskrift (Refereegranskat) 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.
Ort, förlag, år, upplaga, sidor
Elsevier, 2021
Nyckelord
Constraint satisfaction problems, Infinite domains, Partition schemes, Lower bounds
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:liu:diva-175145 (URN)10.1016/j.artint.2021.103505 (DOI)000648650600003 ()
Anmärkning
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-01Bibliografiskt granskad