{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:42:14Z","timestamp":1774946534838,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,9,30]],"date-time":"2017-09-30T00:00:00Z","timestamp":1506729600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Spanish Project MINECO COMMAS","award":["TIN2013-46181-C2-R"],"award-info":[{"award-number":["TIN2013-46181-C2-R"]}]},{"name":"Basque","award":["UFI11\/45"],"award-info":[{"award-number":["UFI11\/45"]}]},{"name":"FRQNT and NSERC"},{"name":"Basque Project","award":["GIU15\/30"],"award-info":[{"award-number":["GIU15\/30"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2017,9,30]]},"abstract":"<jats:p>The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variables satisfying all of the constraints. One formulation of the CSP is as the problem of deciding, given a pair (G \u210d) of relational structures, whether or not there is a homomorphism from the first structure to the second structure. The CSP is generally NP-hard; a common way to restrict this problem is to fix the second structure \u210d so that each structure \u210d gives rise to a problem CSP(\u210d). The problem family CSP(\u210d) has been studied using an algebraic approach, which links the algorithmic and complexity properties of each problem CSP(\u210d) to a set of operations, the so-called polymorphisms of \u210d. Certain types of polymorphisms are known to imply the polynomial-time tractability of CSP(\u210d), and others are conjectured to do so. This article systematically studies\u2014for various classes of polymorphisms\u2014the computational complexity of deciding whether or not a given structure \u210d admits a polymorphism from the class. Among other results, we prove the NP-completeness of deciding a condition conjectured to characterize the tractable problems CSP(\u210d), as well as the NP-completeness of deciding if CSP(\u210d) has bounded width.<\/jats:p>","DOI":"10.1145\/3134757","type":"journal-article","created":{"date-parts":[[2017,10,4]],"date-time":"2017-10-04T18:06:01Z","timestamp":1507140361000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Asking the Metaquestions in Constraint Tractability"],"prefix":"10.1145","volume":"9","author":[{"given":"Hubie","family":"Chen","sequence":"first","affiliation":[{"name":"Universidad del Pa\u00eds Vasco and IKERBASQUE, Basque Foundation for Science, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benoit","family":"Larose","sequence":"additional","affiliation":[{"name":"Champlain Regional College and Universit\u00e9 du Qu\u00e9bec a Montr\u00e9al"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.11.001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exu070"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.32"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-015-0338-z"},{"key":"e_1_2_1_6_1","unstructured":"Libor Barto Jakub Oprsal and Michael Pinsker. 2015. The wonderland of reflections. arXiv:1510.04521.  Libor Barto Jakub Oprsal and Michael Pinsker. 2015. The wonderland of reflections. arXiv:1510.04521."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-04874-0"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-007-2026-0"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exp025"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.059"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.05.003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.008"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628957"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970400"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_4"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI\u201916)","author":"Carbonnel C.","year":"2016","unstructured":"C. Carbonnel . 2016 . The meta-problem for conservative Mal\u2019tsev constraints . In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI\u201916) . C. Carbonnel. 2016. The meta-problem for conservative Mal\u2019tsev constraints. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI\u201916)."},{"key":"e_1_2_1_20_1","unstructured":"Catarina Carvalho and Andrei Krokhin. 2016. On algebras with many symmetric operations. arXiv:1406.5061.  Catarina Carvalho and Andrei Krokhin. 2016. On algebras with many symmetric operations. arXiv:1406.5061."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-005-7031-4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-011-0125-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2340820.2340825"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30201-8_16"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exr039"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.003"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2540090"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/647486.726506"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199383353"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.12.001"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/090775646"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00022-8"},{"key":"e_1_2_1_34_1","unstructured":"Alexandr Kazda. 2011. CSP for binary conservative relational structures. arXiv:1112.1099.  Alexandr Kazda. 2011. CSP for binary conservative relational structures. arXiv:1112.1099."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2010.11.002"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-014-0289-9"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-015-0327-2"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090274"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.048"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9248-9"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208008"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-010-0082-3"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-1-93-104"},{"key":"e_1_2_1_45_1","volume-title":"Research and Exposition in Mathematics. Heldermann Verlag","author":"Szendrei A.","year":"1992","unstructured":"A. Szendrei . 1992 . A survey on strictly simple algebras and minimal varieties . In Research and Exposition in Mathematics. Heldermann Verlag , Berlin, Germany. 209--239. A. Szendrei. 1992. A survey on strictly simple algebras and minimal varieties. In Research and Exposition in Mathematics. Heldermann Verlag, Berlin, Germany. 209--239."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-2009-023-2"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3134757","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3134757","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:24Z","timestamp":1750212684000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3134757"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,30]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9,30]]}},"alternative-id":["10.1145\/3134757"],"URL":"https:\/\/doi.org\/10.1145\/3134757","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,30]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}