{"entities":{"Q485113":{"pageid":486880,"ns":120,"title":"Item:Q485113","lastrevid":62192148,"modified":"2026-04-11T04:23:08Z","type":"item","id":"Q485113","labels":{"en":{"language":"en","value":"An algebraic hardness criterion for surjective constraint satisfaction."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6384900"}},"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":"Q485113$93E65735-F481-481A-B0A4-96DDBA7FE6DB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6e328c250e9e48db8319a9fb70612a6220d75d27","datavalue":{"value":{"text":"An algebraic hardness criterion for surjective constraint satisfaction.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q485113$6158B6C5-BBFC-42BE-BD49-EE208C9864D1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5a4333c61a48e3c129bef833a23e6ac86e2cca4b","datavalue":{"value":"1308.08001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q485113$A1DE6BE7-52C7-46E2-847D-D29DEF1B4967","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"de68fabe0331b50e2c0babeac4b29f27d03cc1ad","datavalue":{"value":{"entity-type":"item","numeric-id":361801,"id":"Q361801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q485113$E3EE5E7F-A7B3-496E-B715-848474DED611","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":"Q485113$B5673D99-4F75-4E9A-8D8E-2C6FB366F12A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bd7ba69d7066824c61c2338d47523cfe00b021ae","datavalue":{"value":{"time":"+2015-01-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q485113$92B0FEE0-5BFA-4E66-A8ED-CFF7C441FD18","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"11b8597f9285272d81c1b5b16ffb742e3383162c","datavalue":{"value":"https://arxiv.org/abs/1405.4917","type":"string"},"datatype":"url"},"type":"statement","id":"Q485113$E94F9738-E007-4619-AEB0-C8C764650C6B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"730722a6aa3295371d99b63ff03f1e51e41f594a","datavalue":{"value":"The constraint satisfaction problem (CSP) on a relational structure \\(B\\) is to decide, given a set of constraints on variables where the relations come from \\(B\\), whether or not there is an assignment to the variables satisfying all of the constraints. The surjective CSP is the variant where one decides the existence of a surjective satisfying assignment onto the universe of \\(B\\). Equivalently, given a structure \\(A\\) over the signature of \\(B\\), one can decide whether or not there is a surjective homomorphism from \\(A\\) to \\(B\\). Main result: Suppose \\(B\\) is a finite structure which is not a singleton. If each polymorphism of \\(B\\) is essentially unary then the surjective CSP on \\(B\\) is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q485113$54DE3F48-F524-41E8-8F7C-A1EE36662513","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"967efbf7e9159f2448c17bb8438ae3fe0ce8fb52","datavalue":{"value":{"entity-type":"item","numeric-id":334969,"id":"Q334969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q485113$308860BC-0603-46EF-B7AD-745E07673C12","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"20bb5571a1bc4300de51d23c463eb631840cb343","datavalue":{"value":"08A70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q485113$298A4C53-124D-4D7D-B416-3CAC462B7BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ed4ac44229a63771ae4ded31038fe93f434bffb7","datavalue":{"value":"03C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q485113$CB90757F-325A-4A79-900E-3AE627C78BCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q485113$39A189BD-336A-4DD3-862E-564F2123B20D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3634cf68b83d5b6bdf3104de35c94fc58d81f010","datavalue":{"value":"6384900","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q485113$E6CE8F5D-85D6-42FC-8EA7-A3844ACB9E73","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a348f9efcaabdd35d491583f05dde8d8e0eb673","datavalue":{"value":"constraint satisfaction problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q485113$36D0AB38-9F61-4E00-8B08-2D6575B6C193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a3da0ccc101f9cdab03142a65cc10df0477037","datavalue":{"value":"surjective constraint satisfaction","type":"string"},"datatype":"string"},"type":"statement","id":"Q485113$575AA7FC-E810-40D1-864F-771FB8EB3D94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d32b0bcc7bb39c92b92984e1db79a0a14ddfb744","datavalue":{"value":"clones","type":"string"},"datatype":"string"},"type":"statement","id":"Q485113$99E4F78F-9A97-4C90-96FA-D88D72E6E900","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":"Q485113$056F2EDC-29B4-4132-921D-5F2613CBF282","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cce4f5a9f12fcab2a41c0f0c6d946072d7f04192","datavalue":{"value":"W2038274600","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q485113$F29B75A5-DE3B-4AE9-A21D-3D902270EEEE","rank":"normal"}],"P223":[{"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":"Q485113$2DDBAB8E-815C-49CA-B2A3-49B8A7C837D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5648006f68a55609d2d936a24b249973ce22b9c","datavalue":{"value":{"entity-type":"item","numeric-id":5390586,"id":"Q5390586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q485113$4FBF280C-EB57-41C3-A886-8F105B5ACDA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f92a64324b680cc8236beb143a28fcd1f34aade6","datavalue":{"value":{"entity-type":"item","numeric-id":444433,"id":"Q444433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q485113$A8B32960-1B07-40ED-9CD3-9E266BACC15C","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":"Q485113$926C7E04-A684-4217-9139-238A66C63CF3","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":"Q485113$BF6BE797-DF4C-4FA3-9802-27A1E356C17A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1858e829edbff20ad48edab5cf07bdd922098408","datavalue":{"value":{"entity-type":"item","numeric-id":4389761,"id":"Q4389761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q485113$12A2788E-D351-4A49-B4E5-8CEB3A76BF75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b330a1fcd57ed03b5bb7894b903390953871d98","datavalue":{"value":{"entity-type":"item","numeric-id":2723175,"id":"Q2723175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q485113$39352956-181F-4D38-8DE3-AC020CDB2D51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f37d2e08a43a48bd48d3a6030daeff555ac5360","datavalue":{"value":{"entity-type":"item","numeric-id":714844,"id":"Q714844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q485113$939E4F8A-3E38-4B6B-A4AA-D9A6F57EADB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5832afc38ab8bf18ff401e331f57661d7337e3b","datavalue":{"value":{"entity-type":"item","numeric-id":2509761,"id":"Q2509761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q485113$2E616213-3671-468E-B30A-15D6F597AB11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e34b0c06a2f0fc97566a9c773b048715652eaed4","datavalue":{"value":{"entity-type":"item","numeric-id":4899300,"id":"Q4899300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q485113$503F498C-7942-4E14-8506-8E65CB65D582","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b11ba29cdf110df41a706cac8bdb7871c2effe09","datavalue":{"value":"10.1007/S00012-014-0308-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q485113$D5BB71FE-E241-4D73-9B77-46C339A930AC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"109db63ffdf79ca806ec3df728dd498092aeead6","datavalue":{"value":{"entity-type":"item","numeric-id":3365840,"id":"Q3365840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"055b6d5f6eeb5457d9642cf8ec016547bfba7009","datavalue":{"value":{"amount":"+0.88287705","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q485113$9E3A4C94-E34B-4CE0-B3CC-C434A9B7AC55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ec4071e457899923dfc5cc9e5b5536f5c7fc07e","datavalue":{"value":{"entity-type":"item","numeric-id":5428815,"id":"Q5428815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b36ebc9c0438c2986e5b425b75918b1a20e95c18","datavalue":{"value":{"amount":"+0.881268","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q485113$9B9406D6-4674-4F8F-81FB-7D4458C14AF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bb88a3db3831831386679eb10379976cbaae2c9","datavalue":{"value":{"entity-type":"item","numeric-id":1014634,"id":"Q1014634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5e04b0eb49c88b10296def0be5e56bc70907657","datavalue":{"value":{"amount":"+0.8812679","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q485113$6E7090B7-E6B7-49FF-AAE1-A8670FC537E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62e70c80621a55f01f31c0cf3923ab4cfb2ca5b1","datavalue":{"value":{"entity-type":"item","numeric-id":3489451,"id":"Q3489451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a836a9652fd6d6b58e860ed2fde2c18d78839219","datavalue":{"value":{"amount":"+0.86258","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q485113$D92B6ACF-6076-406E-AA39-95869E16D45A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80b796c4bac849eb9a553241c3c3ad943cdf07b0","datavalue":{"value":{"entity-type":"item","numeric-id":4221348,"id":"Q4221348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f685fc25b25a629e3052b4faf5591724f9f4ff72","datavalue":{"value":{"amount":"+0.85978967","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q485113$4963B216-D5BA-4A0B-B3B6-6206CC4A314D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73b57d8aec923314cca7f8790df01ff30f6de81f","datavalue":{"value":{"entity-type":"item","numeric-id":2754150,"id":"Q2754150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13543631bb6db8d345ac543c8f5fd72c7690bb30","datavalue":{"value":{"amount":"+0.85098624","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q485113$311F12C8-8103-4E4E-A72C-3951537CC55E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"195e599c04450853ab343d3f252db97ff634775c","datavalue":{"value":{"entity-type":"item","numeric-id":5902002,"id":"Q5902002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bdfd6e712ca84e82f6b409e16c9823ae6515e8b","datavalue":{"value":{"amount":"+0.8500711","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q485113$94F9B5E2-D515-47DD-BA5F-BCBA30A6CFB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b091c6ad307ef3a1494f08534f9ebaa1f6a70509","datavalue":{"value":{"entity-type":"item","numeric-id":5318246,"id":"Q5318246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23ed819fde178c405a212ffdc50565de1725ff2f","datavalue":{"value":{"amount":"+0.8470496","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q485113$A55978D1-32A0-4C27-90CC-7ECE383C31B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee9afb024e39224c0be1395ec9a94a17a985b352","datavalue":{"value":{"entity-type":"item","numeric-id":4729350,"id":"Q4729350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70c0fd9dfbebf5cbf6bc7f425f205514ad5adfe2","datavalue":{"value":{"amount":"+0.84653336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q485113$546EA971-FD56-4DB8-8770-38CCB3EC4D16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcb83f6b51d43ab55fc7c42a5c713896cd6cb8b2","datavalue":{"value":{"entity-type":"item","numeric-id":5111218,"id":"Q5111218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f327dc051ee09731b76843e2d8568146f8f90f68","datavalue":{"value":{"amount":"+0.84612083","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q485113$49E592CB-575C-466E-8C8E-A34440F7D3CD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An algebraic hardness criterion for surjective constraint satisfaction.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_algebraic_hardness_criterion_for_surjective_constraint_satisfaction."}}}}}