Abstract
Many computational problems arising in, for instance, artificial intelligence can be realized as infinitedomain 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 NPhardness 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 exponentialtime 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 firstorder definable constraint languages. We prove that such CSPs are NPhard 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.
BibTeX  Entry
@InProceedings{jonsson_et_al:LIPIcs:2018:9625,
author = {Peter Jonsson and Victor Lagerkvist},
title = {{Why are CSPs Based on Partition Schemes Computationally Hardl}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {43:143:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9625},
URN = {urn:nbn:de:0030drops96257},
doi = {10.4230/LIPIcs.MFCS.2018.43},
annote = {Keywords: Constraint satisfaction problems, infinite domains, partition schemes, lower bounds}
}
Keywords: 

Constraint satisfaction problems, infinite domains, partition schemes, lower bounds 
Collection: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) 
Issue Date: 

2018 
Date of publication: 

27.08.2018 