Document Open Access Logo

Why are CSPs Based on Partition Schemes Computationally Hard?

Authors Peter Jonsson, Victor Lagerkvist

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.43.pdf
  • Filesize: 493 kB
  • 15 pages

Document Identifiers

Author Details

Peter Jonsson
  • Department of Computer and Information Science, Linköping University, Linköping, Sweden
Victor Lagerkvist
  • Department of Computer and Information Science, Linköping University, Linköping, Sweden

Cite As Get BibTex

Peter Jonsson and Victor Lagerkvist. Why are CSPs Based on Partition Schemes Computationally Hard?. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.43

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Constraint satisfaction problems
  • infinite domains
  • partition schemes
  • lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Alber, H. Fernau, and R. Niedermeier. Parameterized complexity: exponential speed-up for planar graph problems. J. Algorithms, 52(1):26-56, 2004. Google Scholar
  2. J. F. Allen. Maintaining knowledge about temporal intervals. Commun. ACM, 26(11):832-843, 1983. Google Scholar
  3. S. Arora, B. Barak, and D. Steurer. Subexponential algorithms for unique games and related problems. J. ACM, 62(5):42:1-42:25, 2015. Google Scholar
  4. M. Bodirsky and V. Dalmau. Datalog and constraint satisfaction with infinite templates. J. Comput. Syst. Sci., 79(1):79-100, 2013. Google Scholar
  5. M. Bodirsky and P. Jonsson. A model-theoretic view on qualitative constraint reasoning. J. Artif. Intell. Res. (JAIR), 58:339-385, 2017. Google Scholar
  6. A. Bulatov. A dichotomy theorem for nonuniform CSPs. In Proc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS-2017), pages 319-330, 2017. Google Scholar
  7. R. de Haan, I. A. Kanj, and S. Szeider. On the subexponential-time complexity of CSP. J. Artif. Intell. Res., 52:203-234, 2015. Google Scholar
  8. I. Düntsch. Relation algebras and their application in temporal and spatial reasoning. Artif. Intell. Rev, 23(4):315-357, Jun 2005. Google Scholar
  9. F. Dylla, J. H. Lee, T. Mossakowski, T. Schneider, A. van Delden, J. van de Ven, and D. Wolter. A survey of qualitative spatial and temporal calculi: Algebraic and computational properties. ACM Comput. Surv., 50(1):7:1-7:39, 2017. Google Scholar
  10. C. Einarson. An extension of the PPSZ algorithm to infinite-domain constraint satisfaction problems. Master’s thesis report, Department of Computer and Information Science, Linköpings Universitet, 2017. Google Scholar
  11. T. Feder and M. Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput., 28(1):57-104, 1998. Google Scholar
  12. M. Grigni, D. Papadias, and C. H. Papadimitriou. Topological inference. In Proc. 14th International Joint Conference on Artificial Intelligence (IJCAI-1995), pages 901-907, 1995. Google Scholar
  13. H. Güsgen. Spatial reasoning based on Allen’s temporal logic. Technical report ICSI TR89-049, International Computer Science Institute, 1993. Google Scholar
  14. T. Hertli, I. Hurbain, S. Millius, R. A. Moser, D. Scheder, and M. Szedlák. The PPSZ algorithm for constraint satisfaction problems on more than two colors. In Proc. 22nd International Conference on Principles and Practice of Constraint Programming (CP-2016), pages 421-437, 2016. Google Scholar
  15. R. Impagliazzo and R. Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  16. P. Jonsson and V. Lagerkvist. An initial study of time complexity in infinite-domain constraint satisfaction. Artif. Intell., 245:115-133, 2017. Google Scholar
  17. P. Jonsson, V. Lagerkvist, G. Nordh, and B. Zanuttini. Strong partial clones and the time complexity of SAT problems. J. Comput. Syst. Sci., 84:52-78, 2017. Google Scholar
  18. A. Krokhin, P. Jeavons, and P. Jonsson. Reasoning about temporal relations: The tractable subclasses of Allen’s interval algebra. J. ACM, 50(5):591-640, 2003. Google Scholar
  19. V. Lagerkvist and M. Wahlström. Kernelization of constraint satisfaction problems: A study through universal algebra. In Proc. 23rd International Conference on Principles and Practice of Constraint Programming (CP-2017), pages 157-171, 2017. Google Scholar
  20. G. Ligozat and J. Renz. What is a qualitative calculus? A general framework. In Proc. 8th Pacific Rim International Conference on Artificial Intelligence (PRICAI-2004), pages 53-64, 2004. Google Scholar
  21. R. Moratz, J. Renz, and D. Wolter. Qualitative spatial reasoning about line segments. In Proc. 14th European Conference on Artificial Intelligence (ECAI-2000), pages 234-238, 2000. Google Scholar
  22. A. Mukerjee and G. Joe. A qualitative model for space. In Proc. 8th National Conference on Artificial Intelligence (AAAI-1990), pages 721-727, 1990. Google Scholar
  23. J. Opatrny. Total ordering problem. SIAM J. Comput., 8(1):111-114, 1979. Google Scholar
  24. J. Renz. Qualitative spatial and temporal reasoning: Efficient algorithms for everyone. In Proc. 20th International Joint Conference on Artifical Intelligence (IJCAI-2007), pages 526-531, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc. Google Scholar
  25. J. Renz and J. J. Li. Automated complexity proofs for qualitative spatial and temporal calculi. In Proc. Principles of Knowledge Representation and Reasoning (KR-2008), pages 715-723, 2008. Google Scholar
  26. J. Renz and B. Nebel. On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus. Artif. Intell., 108(1-2):69-123, 1999. Google Scholar
  27. J. Renz and B. Nebel. Qualitative spatial reasoning using constraint calculi. In Marco Aiello, Ian Pratt-Hartmann, and Johan van Benthem, editors, Handbook of Spatial Logics, pages 161-215. Springer, 2007. Google Scholar
  28. R. Santhanam and S. Srinivasan. On the limits of sparsification. In Proc. 39th International Colloquium on Automata, Languages, and Programming (ICALP-2012), pages 774-785, 2012. Google Scholar
  29. P. Traxler. The time complexity of constraint satisfaction. In Proc. 3rd International Workshop on Parameterized and Exact Computation (IWPEC-2008), pages 190-201, 2008. Google Scholar
  30. D. Zhuk. A proof of CSP dichotomy conjecture. In Proc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS-2017), pages 331-342, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact