{"entities":{"Q2634708":{"pageid":2645451,"ns":120,"title":"Item:Q2634708","lastrevid":57965148,"modified":"2026-04-03T06:39:50Z","type":"item","id":"Q2634708","labels":{"en":{"language":"en","value":"CSP for binary conservative relational structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6542177"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$FB9D2113-8DD1-4B99-836B-1AAD601DB5D1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b09c62ea26b852b7db276c63a735fb6be8b0cabe","datavalue":{"value":{"text":"CSP for binary conservative relational structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2634708$464E2C71-791B-454D-AF3A-2480FCAEE73E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"66f6ef3d9de7fdb9a616f96d218dda66e333a286","datavalue":{"value":"1356.08001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2634708$51D36215-5A3E-417C-88AB-92501083F01B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1d1739800c64a45953cea3eb646f5e4ea0d6dded","datavalue":{"value":{"entity-type":"item","numeric-id":590310,"id":"Q590310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$1E7C2E43-2FD6-4A9E-AEA1-7E844F8B2BCD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8fa179c8715004e2374d4db0c3ce41b39558e95d","datavalue":{"value":{"entity-type":"item","numeric-id":178112,"id":"Q178112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$7DDC0BFE-2258-4A5A-9B6B-B5283268115F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c0fbb1c99210203060d83e8748755157d2741267","datavalue":{"value":{"time":"+2016-02-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2634708$41DD8D8C-4379-4937-8E32-8A712EC2AEF7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d7b09cbee7389fdd7cc05371be8e174ae2e98e89","datavalue":{"value":"https://arxiv.org/abs/1112.1099","type":"string"},"datatype":"url"},"type":"statement","id":"Q2634708$65AC82A8-E7C7-481A-880F-1B1759EE43C2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ab0c0a78d2a519716da0470e585ea3c6e7b8d63b","datavalue":{"value":"For a fixed finite relational structure \\(\\mathbb A\\), the nonuniform Constraint Satisfaction Problem (\\(\\mathrm{CSP}(\\mathbb A)\\)) asks whether a given input structure \\(\\mathbb X\\) admits a homomorphism to \\(\\mathbb A\\). This problem received a lot of attention following \\textit{T. Feder} and \\textit{M. Y. Vardi}'s conjecture P versus NP-complete dichotomy [SIAM J. Comput. 28, No. 1, 57--104 (1998; Zbl 0914.68075)] and the development of the so-called algebraic approach: using polymorphisms of \\(\\mathbb A\\) to control the complexity of \\(\\mathrm{CSP}(\\mathbb A)\\). The algebraic dichotomy conjecture [\\textit{A. Bulatov} et al., SIAM J. Comput. 34, No. 3, 720--742 (2005; Zbl 1071.08002)] states that if a core structure \\(\\mathbb A\\) admits a Taylor polymorphism, then \\(\\mathrm{CSP}(\\mathbb A)\\) is in P, and otherwise it is NP-complete.  One of the major successful steps towards resolving this conjecture was the case of conservative structures (also known as the list homomorphism problem) [\\textit{A. A. Bulatov}, ACM Trans. Comput. Log. 12, No. 4, Article No. 24, 66 p. (2011; Zbl 1351.68113)]. In [\\textit{P. Hell} and \\textit{A. Rafiey}, ``The dichotomy of list homomorphisms for digraphs'', in: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23--25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1703--1713 (2011; \\url{doi:10.1137/1.9781611973082.131})], combinatorial methods were used to characterize conservative digraphs with tractable CSP. Moreover, the authors proved that all of them can be solved using local consistency checking (so-called bounded width).  In this paper, combinatorial ideas from the digraph case are combined with advanced algebraic techniques from the general case to obtain a short and elegant proof of the CSP dichotomy for binary 3-conservative structures (that is, at most binary relations and every at most 3-element subset is a unary relation). The main result is the following: If a binary 3-conservative structure admits a Taylor polymorphism, then its polymorphism algebra generates a congruence meet semidistributive variety. As a consequence, all tractable cases have bounded width, as is the case with conservative digraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2634708$DFB8CD52-EBBB-429A-BBC7-F7383F22EF2C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a6645710af3c138f5110cb84c5347f40b4175ae7","datavalue":{"value":{"entity-type":"item","numeric-id":1686249,"id":"Q1686249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$6FF9DCC7-F541-4CF5-A72D-76F334175F55","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"92a555e3a541c9f0978c54443cf0a96e2a43c4df","datavalue":{"value":"08A02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2634708$E98C1B7A-C3EF-4741-84FA-103B19480A10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ed4ac44229a63771ae4ded31038fe93f434bffb7","datavalue":{"value":"03C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2634708$209EB276-1DD5-4C10-8C19-D9012EA64A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"308ceb1553bd4b03ccb725c738254e73fff25edb","datavalue":{"value":"08A30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2634708$5AC3B014-456B-42CB-AAEF-5FF61C35D439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2634708$064286A0-A7A7-44AC-93E9-3E57FADD7390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2634708$A45E3598-6D22-41D6-BEEC-BCCD0557F68E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"642f882d062964cf1ea2901f7bb4297f8265b1fd","datavalue":{"value":"6542177","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2634708$BAE8A401-E9A7-4F1F-A3B6-2B4FA3B7F008","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8df6300f73d180e9266d2917092f3cb92e327711","datavalue":{"value":"meet-semidistributivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2634708$9FFAB135-0A3E-4C7D-B653-F611224AED14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e2919efda3d9828b76deb30a63d62ca5b413914","datavalue":{"value":"clone","type":"string"},"datatype":"string"},"type":"statement","id":"Q2634708$43B75859-B7D0-4FE2-8BFD-665BCE1CE8C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a348f9efcaabdd35d491583f05dde8d8e0eb673","datavalue":{"value":"constraint satisfaction problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2634708$DD41B4D3-CC2E-4E8E-9D26-F6F390988DDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"17d6e190b2fe055a893e7c0e6cd62a7bf2161ccf","datavalue":{"value":"weak near unanimity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2634708$B48A4CEA-D0FF-4768-8FA3-E635DAEA63DF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$00AF95F7-6565-4B68-91F6-D0B694C1A96D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e77d464f62baed3782c17e7063d8a24cef73155d","datavalue":{"value":"W3105727132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2634708$500135EF-B55F-4351-97B4-FE0FB0344CBA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b07f2784b57531e73555367712e3ac49b3a2f090","datavalue":{"value":{"entity-type":"item","numeric-id":2427534,"id":"Q2427534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$81C04526-633A-4154-BCA2-2AC6BBEC05A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca78002dcebbe568a6f1d4cfe070a6f048fc91ff","datavalue":{"value":{"entity-type":"item","numeric-id":1014634,"id":"Q1014634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$D61C5E6A-998E-46C5-913A-AA7BC824D16D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9507be843b682c74b6e88d6f61472b28c2047f2b","datavalue":{"value":{"entity-type":"item","numeric-id":5171200,"id":"Q5171200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$1B8E5E9D-3EB7-498E-8DF2-7061CA6D3EF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17329aeb7c77f3079291a06d18c322c312b1a335","datavalue":{"value":{"entity-type":"item","numeric-id":2946643,"id":"Q2946643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$D440CE19-6807-4D14-8C5D-E4DCC9441C53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d9d5f067eb958341991b2ee01dc0caab581f808","datavalue":{"value":{"entity-type":"item","numeric-id":5317171,"id":"Q5317171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$C4E0441C-796A-46CD-BDA9-F0F024279E82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11170f9c7128eb081349dcdf84e1ea3bf4e88abf","datavalue":{"value":{"entity-type":"item","numeric-id":5415454,"id":"Q5415454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$DE341F9A-D223-43CC-BF3C-228682AFAEC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ddbd5ace5579af28195b888b66e44987be3a6e7","datavalue":{"value":{"entity-type":"item","numeric-id":2536623,"id":"Q2536623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$671F33DA-E5C7-437C-A6F7-4B10110E4C02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa7547a0cbf586eca1f0145ca7b154931657b2e4","datavalue":{"value":{"entity-type":"item","numeric-id":5365149,"id":"Q5365149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$62E057D7-A96C-43C5-9285-2E5F1B1E196E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75e01bd225cc1eaadd4b3b359e2717f21721c442","datavalue":{"value":{"entity-type":"item","numeric-id":4040245,"id":"Q4040245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$49305D4F-B008-47B7-8194-28123C2DDEBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6942914cdcc770c70ed5e1a97e4b25b80b84b4a","datavalue":{"value":{"entity-type":"item","numeric-id":4979155,"id":"Q4979155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$A8290D99-AA22-438C-A696-1476694FBE79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2576ed093c49c3a19e4ccfb584b3c402462cb50","datavalue":{"value":{"entity-type":"item","numeric-id":2351504,"id":"Q2351504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$5D016DFC-CAE3-4530-ACED-A5CBB2B16D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd2c5f3d0361666f0b4f32c95e10fbb3963a30a7","datavalue":{"value":{"entity-type":"item","numeric-id":3874283,"id":"Q3874283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$DD1E4CE2-4560-4AA2-A6AF-1D7CA66D34E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2634708$ACC62997-710D-43F2-8A69-A064F98F35C5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2dbc5a199474e3f0d7900d3cb3671f9754a543e5","datavalue":{"value":"10.1007/S00012-015-0358-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2634708$3568A9DC-4DED-4FE8-938E-E6AD14DCEFF3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6714c4adb1f939a57198195e72d0ddcbcee2ba5","datavalue":{"value":{"entity-type":"item","numeric-id":896026,"id":"Q896026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1e99afbaeed84fa6dbf94a256f077d53d9b7e76","datavalue":{"value":{"amount":"+0.7809776663780212","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2634708$8AF92766-DA19-472B-9C6A-1E239280A281","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b34a42074bc0788f0e2e10ed398d7b64830bb0df","datavalue":{"value":{"entity-type":"item","numeric-id":4973888,"id":"Q4973888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2b64946b1c476dc6b74b23a06cb190de6e272a2","datavalue":{"value":{"amount":"+0.7752211689949036","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2634708$FEA6958D-20CD-4386-AC6E-4D9605AF19DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bd019c629ca81ec5077da5d3452975c7454def7","datavalue":{"value":{"entity-type":"item","numeric-id":4635925,"id":"Q4635925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a68a18beac94904f20f062fc8df9afb6b52a78cd","datavalue":{"value":{"amount":"+0.7674673199653625","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2634708$5109F214-8CFD-4FB6-90F5-375DCFD94B29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4289273cf2889a7717925050514ff7008d6fd248","datavalue":{"value":{"entity-type":"item","numeric-id":3398315,"id":"Q3398315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7167eb87f2db1f419232bafc891e1dcf528aae46","datavalue":{"value":{"amount":"+0.7602094411849976","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2634708$EC842706-666C-4156-94A7-03B8513F0F69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de8a7c62c7ed05a4958a9d2b53fa2cca7fc564e8","datavalue":{"value":{"entity-type":"item","numeric-id":485113,"id":"Q485113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba96d4140c01b0d638299062fa967d943d827f05","datavalue":{"value":{"amount":"+0.7586819529533386","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2634708$AA141B91-71ED-43FC-80BD-70BD5BA2A2C7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2634708","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2634708"}}}}}