Document Open Access Logo

Finitely Tractable Promise Constraint Satisfaction Problems

Authors Kristina Asimi, Libor Barto

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.11.pdf
  • Filesize: 0.74 MB
  • 16 pages

Document Identifiers

Author Details

Kristina Asimi
  • Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague, Czechia
Libor Barto
  • Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague, Czechia

Funding

Both authors have received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No 771005).

Cite As Get BibTex

Kristina Asimi and Libor Barto. Finitely Tractable Promise Constraint Satisfaction Problems. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.11

Abstract

The Promise Constraint Satisfaction Problem (PCSP) is a generalization of the Constraint Satisfaction Problem (CSP) that includes approximation variants of satisfiability and graph coloring problems. Barto [LICS '19] has shown that a specific PCSP, the problem to find a valid Not-All-Equal solution to a 1-in-3-SAT instance, is not finitely tractable in that it can be solved by a trivial reduction to a tractable CSP, but such a CSP is necessarily over an infinite domain (unless P=NP). We initiate a systematic study of this phenomenon by giving a general necessary condition for finite tractability and characterizing finite tractability within a class of templates - the "basic" tractable cases in the dichotomy theorem for symmetric Boolean PCSPs allowing negations by Brakensiek and Guruswami [SODA'18].

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Constraint and logic programming
Keywords
  • Constraint satisfaction problems
  • promise constraint satisfaction
  • Boolean PCSP
  • polymorphism
  • finite tractability
  • homomorphic relaxation

Metrics

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

References

  1. Per Austrin, Venkatesan Guruswami, and Johan Håstad. (2+ε)-Sat is NP-hard. SIAM J. Comput., 46(5):1554-1573, 2017. URL: https://doi.org/10.1137/15M1006507.
  2. L. Barto. Promises make finite (constraint satisfaction) problems infinitary. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-8, 2019. Google Scholar
  3. Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Oprsal. Algebraic approach to promise constraint satisfaction. CoRR, abs/1811.00970, 2018. URL: http://arxiv.org/abs/1811.00970.
  4. Libor Barto and Marcin Kozik. Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Log. Methods Comput. Sci., 8(1:07):1-26, 2012. Special issue: Selected papers of the Conference "Logic in Computer Science (LICS) 2010". URL: https://doi.org/10.2168/LMCS-8(1:07)2012.
  5. Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Andrei Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.1.
  6. Libor Barto, Jakub Opršal, and Michael Pinsker. The wonderland of reflections. Israel Journal of Mathematics, 223(1):363-398, February 2018. URL: https://doi.org/10.1007/s11856-017-1621-9.
  7. Manuel Bodirsky. Constraint satisfaction problems with infinite templates. In Nadia Creignou, Phokion G. Kolaitis, and Heribert Vollmer, editors, Complexity of Constraints, volume 5250 of Lecture Notes in Computer Science, pages 196-228. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-92800-3_8.
  8. Joshua Brakensiek and Venkatesan Guruswami. Promise constraint satisfaction: Structure theory and a symmetric boolean dichotomy. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'18, pages 1782-1801, Philadelphia, PA, USA, 2018. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3174304.3175422.
  9. Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720-742, 2005. URL: https://doi.org/10.1137/S0097539700376676.
  10. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 319-330, October 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  11. Jakub Bulín, Andrei Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st Annual ACM SIGACT Symposium on the Theory of Computing (STOC ’19), New York, NY, USA, 2019. ACM. URL: https://doi.org/10.1145/3313276.3316300.
  12. Guofeng Deng, Ezzeddine El Sai, Trevor Manders, Peter Mayr, Poramate Nakkirt, and Athena Sparks. Sandwiches for promise constraint satisfaction, 2020. URL: http://arxiv.org/abs/2003.07487.
  13. 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 J. Comput., 28(1):57-104, February 1998. URL: https://doi.org/10.1137/S0097539794266766.
  14. Miron Ficak, Marcin Kozik, Miroslav Olsák, and Szymon Stankiewicz. Dichotomy for Symmetric Boolean PCSPs. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 57:1-57:12, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.57.
  15. Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. J. Combin. Theory Ser. B, 48(1):92-110, 1990. Google Scholar
  16. Peter Jeavons. On the algebraic structure of combinatorial problems. Theor. Comput. Sci., 200(1-2):185-204, 1998. Google Scholar
  17. Vladimir Kolmogorov, Andrei Krokhin, and Michal Rolínek. The complexity of general-valued CSPs. SIAM Journal on Computing, 46(3):1087-1110, 2017. Google Scholar
  18. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC '78, pages 216-226, New York, NY, USA, 1978. ACM. URL: https://doi.org/10.1145/800133.804350.
  19. Dmitriy Zhuk. A proof of CSP dichotomy conjecture. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 331-342, October 2017. URL: https://doi.org/10.1109/FOCS.2017.38.
  20. Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5), 2020. URL: https://doi.org/10.1145/3402029.
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