License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.43
URN: urn:nbn:de:0030-drops-96257
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9625/
Go to the corresponding LIPIcs Volume Portal


Jonsson, Peter ; Lagerkvist, Victor

Why are CSPs Based on Partition Schemes Computationally Hard?

pdf-format:
LIPIcs-MFCS-2018-43.pdf (0.5 MB)


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
Seminar: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 20.08.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI