Document Open Access Logo

A Complexity Dichotomy for Poset Constraint Satisfaction

Authors Michael Kompatscher, Trung Van Pham

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.47.pdf
  • Filesize: 479 kB
  • 12 pages

Document Identifiers

Author Details

Michael Kompatscher
Trung Van Pham

Cite As Get BibTex

Michael Kompatscher and Trung Van Pham. A Complexity Dichotomy for Poset Constraint Satisfaction. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 47:1-47:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.47

Abstract

We determine the complexity of all constraint satisfaction problems over partial orders, in particular we show that every such problem is NP-complete or can be solved in polynomial time. This result generalises the complexity dichotomy for temporal constraint satisfaction problems by Bodirsky and Kára. We apply the so called universal-algebraic approach together with tools from model theory and Ramsey theory to prove our result. In the course of this analysis we also establish a structural dichotomy regarding the model theoretic properties of the reducts of the random partial order.

Subject Classification

Keywords
  • Constraint Satisfaction
  • Random Partial Order
  • Computational Complexity
  • Universal Algebra
  • Ramsey Theory

Metrics

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

References

  1. Frank D. Anger. On Lamport’s interprocessor communication model. ACM Transactions on Programming Languages and Systems (TOPLAS), 11(3):404-417, 1989. Google Scholar
  2. Libor Barto and Michael Pinsker. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems, 2016. preprint, arXiv:1602.04353, to appear in the proceedings of LICS 2016. Google Scholar
  3. Manuel Bodirsky. The core of a countably categorical structure. In STACS 2005, pages 110-120. Springer, 2005. Google Scholar
  4. Manuel Bodirsky. Complexity classification in infinite-domain constraint satisfaction, 2012. Mémoire HDR à l'Université Paris 7, arXiv:1201.0856v7. Google Scholar
  5. Manuel Bodirsky, Hubie Chen, Jan Kára, and Timo von Oertzen. Maximal infinite-valued constraint languages. Theoret. Comput. Sci., 410(18):1684-1693, 2009. Google Scholar
  6. Manuel Bodirsky, Peter Jonsson, and Trung Van Pham. The complexity of phylogeny constraint satisfaction. In STACS 16, 2016. Google Scholar
  7. Manuel Bodirsky and Jan Kára. The complexity of equality constraint languages. Theory of Computing Systems, 43(2):136-158, 2008. Google Scholar
  8. Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. Journal of the ACM, 57(2):Art. 9, 41, 2010. Google Scholar
  9. Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz. Constraint satisfaction problems for reducts of homogeneous graphs, 2016. Preprint, arXiv:1602.05819. Google Scholar
  10. Manuel Bodirsky and Jaroslav Nešetřil. Constraint satisfaction with countable homogeneous templates. Journal of Logic and Computation, 16(3):359-373, 2006. Google Scholar
  11. Manuel Bodirsky and Michael Pinsker. Reducts of Ramsey structures. AMS Contemporary Mathematics, vol. 558 (Model Theoretic Methods in Finite Combinatorics), pages 489-519, 2011. Google Scholar
  12. Manuel Bodirsky and Michael Pinsker. Schaefer’s theorem for graphs. J. ACM, 62(3):19:1-19:52, 2015. Google Scholar
  13. Manuel Bodirsky, Michael Pinsker, and Todor Tsankov. Decidability of definability. Journal of Symbolic Logic, 78(4):1036-1054, 2013. Google Scholar
  14. Mathias Broxvall and Peter Jonsson. Point algebras for temporal reasoning: Algorithms and complexity. Artificial Intelligence, 149(2):179-220, 2003. Google Scholar
  15. Peter Cameron. Transitivity of permutation groups on unordered sets. Mathematische Zeitschrift, 148:127-139, 1976. Google Scholar
  16. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM Journal on Computing, 28:57-104, 1999. Google Scholar
  17. Patrice Godefroid, J. van Leeuwen, J. Hartmanis, G. Goos, and Pierre Wolper. Partial-order methods for the verification of concurrent systems: an approach to the state-explosion problem, volume 1032. Springer Heidelberg, 1996. Google Scholar
  18. Wilfrid Hodges. A shorter model theory. Cambridge University Press, Cambridge, 1997. Google Scholar
  19. Peter Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200(1):185-204, 1998. Google Scholar
  20. Michael Kompatscher and Trung Van Pham. A complexity dichotomy for poset constraint satisfaction, 2016. Preprint, arXiv:1603.00082. Google Scholar
  21. Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558-565, 1978. Google Scholar
  22. Leslie Lamport. The mutual exclusion problem: Part I - A theory of interprocess communication. Journal of the ACM, 33(2):313-326, 1986. Google Scholar
  23. Péter Pál Pach, Michael Pinsker, Gabriella Pluhár, András Pongrácz, and Csaba Szabó. Reducts of the random partial order. Advances in Mathematics, 267:94-120, 2014. Google Scholar
  24. Péter Pál Pach, Michael Pinsker, András Pongrácz, and Csaba Szabó. A new operation on partially ordered sets. Journal of Combinatorial Theory, Series A, 120:1450-1462, 2013. Google Scholar
  25. Madelaine Paoli, William T. Trotter, and James W. Walker. Graphs and orders in Ramsey theory and in dimension theory. In Graphs and Order, pages 351-394. Springer, 1985. Google Scholar
  26. Michael Pinsker. Algebraic and model theoretic methods in constraint satisfaction, 2015. preprint, arXiv:1507.00931. Google Scholar
  27. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 216-226. ACM, 1978. Google Scholar
  28. Andrew S. Tanenbaum and Maarten Van Steen. Distributed systems. Prentice-Hall, 2007. Google Scholar
  29. Simon Thomas. Reducts of the random graph. The Journal of symbolic logic, 56(01):176-181, 1991. 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