License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.43
URN: urn:nbn:de:0030-drops-96257
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9625/
Jonsson, Peter ;
Lagerkvist, Victor
Why are CSPs Based on Partition Schemes Computationally Hard?
Abstract
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.
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:1--43:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-086-6},
ISSN = {1868-8969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9625},
URN = {urn:nbn:de:0030-drops-96257},
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 |
