Generalized Majority-Minority Operations are Tractable

Victor Dalmau

doi:10.2168/LMCS-2(4:1)2006

Victor Dalmau - Generalized Majority-Minority Operations are Tractable

lmcs:2237 - Logical Methods in Computer Science, September 28, 2006, Volume 2, Issue 4 - https://doi.org/10.2168/LMCS-2(4:1)2006

Generalized Majority-Minority Operations are TractableArticle

Authors: Victor Dalmau

Generalized majority-minority (GMM) operations are introduced as a common generalization of near unanimity operations and Mal'tsev operations on finite sets. We show that every instance of the constraint satisfaction problem (CSP), where all constraint relations are invariant under a (fixed) GMM operation, is solvable in polynomial time. This constitutes one of the largest tractable cases of the CSP.

https://doi.org/10.2168/LMCS-2(4:1)2006

Source: arXiv.org:cs/0609108

Volume: Volume 2, Issue 4

Published on: September 28, 2006

Submitted on: January 4, 2006

Keywords: Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,F.4.1

Licence: arXiv.org - Assumed non-exclusive license to distribute

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

23 Documents citing this article

Paolo Lipparini, 2022, Between an n-ary and an n + 1-ary near-unanimity term, arXiv (Cornell University), 32, 08, pp. 1595-1614, 10.1142/s0218196723500017, https://arxiv.org/abs/2105.14041.

Alexandr Kazda;Jakub Opršal;Matt Valeriote;Dmitriy Zhuk, 2019, Deciding the Existence of Minority Terms, Durham Research Online (Durham University), 63, 3, pp. 577-591, 10.4153/s0008439519000651, https://dro.dur.ac.uk/31834/1/31834.pdf.

Andrei A. Bulatov, Lecture notes in computer science, Constraint Satisfaction Problems: Complexity and Algorithms, pp. 1-25, 2018, 10.1007/978-3-319-77313-1_1.

Andrei A. Bulatov, 2018, Constraint satisfaction problems, ACM SIGLOG News, 5, 4, pp. 4-24, 10.1145/3292048.3292050, https://doi.org/10.1145/3292048.3292050.

Clément Carbonnel, The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable, pp. 130-146, 2016, 10.1007/978-3-319-44953-1_9, https://hal.science/hal-01413124.

Martin C. Cooper;Stanislav Živný, The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns, pp. 652-661, 2016, New York NY USA, 10.1145/2933575.2933587, https://hal.science/hal-01671341.

Sławomir Lasota, 2016, Equivariant algorithms for constraint satisfaction problems over coset templates, arXiv (Cornell University), 118, pp. 44-52, 10.1016/j.ipl.2016.09.009, http://arxiv.org/abs/1412.4020.

Andrei A. Bulatov, 2015, Conservative constraint satisfaction re-revisited, Journal of Computer and System Sciences, 82, 2, pp. 347-356, 10.1016/j.jcss.2015.07.004, https://doi.org/10.1016/j.jcss.2015.07.004.

Clifford Bergman;David Failing, 2015, Commutative idempotent groupoids and the constraint satisfaction problem, Iowa State University Digital Repository (Iowa State University), 73, 3-4, pp. 391-417, 10.1007/s00012-015-0323-6, https://lib.dr.iastate.edu/etd/13285.

Clément Carbonnel;Martin C. Cooper, 2015, Tractability in constraint satisfaction problems: a survey, 21, 2, pp. 115-144, 10.1007/s10601-015-9198-6, https://hal.archives-ouvertes.fr/hal-01230685.

LIBOR BARTO, 2015, THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA, Bulletin of Symbolic Logic, 21, 3, pp. 319-337, 10.1017/bsl.2015.25.

Libor Barto, 2014, Constraint satisfaction problem and universal algebra, ACM SIGLOG News, 1, 2, pp. 14-24, 10.1145/2677161.2677165, https://doi.org/10.1145/2677161.2677165.

Stanislav Živný, Cognitive technologies, Tractable Languages, pp. 117-124, 2012, 10.1007/978-3-642-33974-5_6.

Stanislav Živný, Cognitive technologies, Background, pp. 3-27, 2012, 10.1007/978-3-642-33974-5_1.

Andrei A. Bulatov, Lecture notes in computer science, On the CSP Dichotomy Conjecture, pp. 331-344, 2011, 10.1007/978-3-642-20712-9_26.

Libor Barto, CiteSeer X (The Pennsylvania State University), The Dichotomy for Conservative Constraint Satisfaction Problems Revisited, 2011, Toronto, ON, Canada, 10.1109/lics.2011.25, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.396.2063.

Libor Barto;Marcin Kozik, 2010 25th Annual IEEE Symposium on Logic in Computer Science, New Conditions for Taylor Varieties and CSP, 1853, pp. 100-109, 2010, Edinburgh, United Kingdom, 10.1109/lics.2010.34.

Catarina Carvalho;Víctor Dalmau;Petar Marković;Miklós Maróti, 2009, CD(4) has bounded width, Algebra Universalis, 60, 3, pp. 293-307, 10.1007/s00012-009-2113-5.

Libor Barto;Marcin Kozik;Todd Niven, 2009, The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell), SIAM Journal on Computing, 38, 5, pp. 1782-1802, 10.1137/070708093.

Andrei A. Bulatov;Matthew A. Valeriote, CiteSeer X (The Pennsylvania State University), Recent Results on the Algebraic Approach to the CSP, pp. 68-92, 2008, 10.1007/978-3-540-92800-3_4, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.151.1332.

Hubie Chen, Lecture notes in computer science, Quantified Constraint Satisfaction and the Polynomially Generated Powers Property, pp. 197-208, 2008, 10.1007/978-3-540-70583-3_17.

E. Kiss;M. Valeriote, arXiv (Cornell University), On Tractability and Congruence Distributivity, pp. 221-230, 2006, Seattle, WA, USA, 10.1109/lics.2006.40, http://arxiv.org/abs/0705.2229.

Manuel Bodirsky;Hubie Chen, Lecture notes in computer science, Collapsibility in Infinite-Domain Quantified Constraint Satisfaction, pp. 197-211, 2006, 10.1007/11874683_13.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1552 times.

This article's PDF has been downloaded 337 times.