{"entities":{"Q6119674":{"pageid":13253981,"ns":120,"title":"Item:Q6119674","lastrevid":56774169,"modified":"2026-03-23T13:40:34Z","type":"item","id":"Q6119674","labels":{"en":{"language":"en","value":"Constraint satisfaction problem: what makes the problem easy"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7823032"}},"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":"Q6119674$B4AC5BB3-B3A3-4B9B-9B62-34645130B2A2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b0533bd6a5f4b049ddc97535a3e8da47917b3662","datavalue":{"value":{"text":"Constraint satisfaction problem: what makes the problem easy","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6119674$B07353A9-739B-4A7E-B424-9A90B15CFED8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"351693e9525940268c4116160b96b589f752def1","datavalue":{"value":{"entity-type":"item","numeric-id":522227,"id":"Q522227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$F5EEF6A5-B2ED-40CA-B200-7B07D6E2B41B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e604ba0becf1eaf60071ff392a9dd3119b76744f","datavalue":{"value":{"entity-type":"item","numeric-id":6118117,"id":"Q6118117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$9EF04700-F2FB-4DBC-BF4E-9BFE0F602AC6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"946f9eb7a7737d88be41a6a799278842b1b41e8e","datavalue":{"value":{"time":"+2024-03-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6119674$A4F0C829-F264-4B5C-B197-F150E38836E7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cfb7be6d1c8ebce2e5eb50a380487117d7e43f68","datavalue":{"value":"Summary: The Constraint Satisfaction Problem is the problem of deciding whether there is an assignment to a set of variables subject to some specified constraints. Systems of linear equations, graph coloring, and many other combinatorial problems can be expressed as Constraint Satisfaction Problems for some constraint language. In 1993 it was conjectured that for any constraint language the problem is either solvable in polynomial time, or NP-complete, and for many years this conjecture was the main open question in the area. After this conjecture was resolved in 2017, we finally can say what makes the problem hard and what makes the problem easy. In the first part of the paper, we give an elementary introduction to the area, explaining how the full classification appeared and why it is formulated in terms of polymorphisms. We discuss what makes the problem NP-hard, what makes the problem solvable by local consistency checking, and explain briefly the main idea of one of the two proofs of the conjecture. The second part of the paper is devoted to the extension of the CSP, called Quantified CSP, where we allow using both universal and existential quantifiers. Finally, we discuss briefly other variants of the CSP, as well as some open questions related to them.  For the entire collection see [Zbl 07816357].","type":"string"},"datatype":"string"},"type":"statement","id":"Q6119674$A333D354-B31B-43BB-B09C-2B38806AB32E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d53cd5ab715340bbfc507bf5b4aac1b907f4465d","datavalue":{"value":"03B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6119674$B4CA6D95-E8A2-4C30-ABDF-A61F67CA2B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"20bb5571a1bc4300de51d23c463eb631840cb343","datavalue":{"value":"08A70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6119674$DCCE03E3-AEC9-4F22-83D4-A684F24D4336","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6119674$BA8CDC7A-871C-4BA1-9D17-5EA675C4C042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6119674$966A34EE-20E0-4B42-919B-41B4C1A34095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"62ae2f4e9717dc72a20d2c4f17bdde30d85a417c","datavalue":{"value":"68T27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6119674$CF8F29D4-C912-4564-B42A-A6941D8B53F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c06e0874e30722381d620ef69fb36c407a01cb04","datavalue":{"value":"03B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6119674$612A129A-8BCD-4E4B-B40F-4B0A4D8711ED","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1ed9e50ed2550be8305a0a72af69d7efe55470ad","datavalue":{"value":"7823032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6119674$4E3B925F-3E33-4D25-AAFA-21673A1E3784","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a348f9efcaabdd35d491583f05dde8d8e0eb673","datavalue":{"value":"constraint satisfaction problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q6119674$D9242F01-6AF2-4081-B807-98DD59A0C5D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6119674$6663153E-7F3D-4B5E-946D-C84C84AF0136","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe324920b7891d39aae439d7c21fee61c31ee0e7","datavalue":{"value":"CSP dichotomy","type":"string"},"datatype":"string"},"type":"statement","id":"Q6119674$807FBA05-D011-4E30-8C80-E96D87E555CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2358c6f306b2f0764b1088130dd2f7274cf9476","datavalue":{"value":"quantified constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q6119674$08CF558C-31D1-48C6-94E4-D6032BE3F13B","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":"Q6119674$459F245A-B760-48B2-89B7-B60B2E1CBD58","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"42c072d9dc3169d977912e7e816a571c8525dab5","datavalue":{"value":"https://doi.org/10.4171/icm2022/125","type":"string"},"datatype":"url"},"type":"statement","id":"Q6119674$4E1D08C7-8D46-49E6-B1F5-14523D7CA36D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e8aba06243c86645c50bb33cf9f3e1ee27b6bf60","datavalue":{"value":"W4389817267","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6119674$2CFA87CD-547C-4972-96BE-B0B12F797FB8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d8653d2e6f53b17cedec7b9470bcf88609d4f1f","datavalue":{"value":{"entity-type":"item","numeric-id":5320667,"id":"Q5320667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$6C48E259-6C4C-4C5A-8B61-BB64ADD45555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"524a128b67098c301f4b4b48ba9c46351e78d895","datavalue":{"value":{"entity-type":"item","numeric-id":1211524,"id":"Q1211524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$75B687ED-C0DA-40D3-BAE0-3DED6A54615A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed83fe1da28146a38afa0befa44c1b2681b1778b","datavalue":{"value":{"entity-type":"item","numeric-id":2881074,"id":"Q2881074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$BE1CDBA3-107A-4598-AE2A-F38E2787E70A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9efad9f5c600be8cd025ec5c46270403c80fd1bb","datavalue":{"value":{"entity-type":"item","numeric-id":3189638,"id":"Q3189638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$E2BC8861-41F9-4775-A299-91AA5A5A794F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19e2aa9f6a4eb970f9ffbb9cc6da69541b953c20","datavalue":{"value":{"entity-type":"item","numeric-id":4993594,"id":"Q4993594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$81A8431B-0E2A-4C80-9D64-21BD4DE764BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c1ff3bbdad58ba73d223d82904d17dd65746329","datavalue":{"value":{"entity-type":"item","numeric-id":1709740,"id":"Q1709740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$D76C5901-3698-4E88-8947-45AB7D19963D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cf495049c97efeee8513ace897fd2d3339f6dfa","datavalue":{"value":{"entity-type":"item","numeric-id":3550542,"id":"Q3550542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$18032A82-79D2-4FF7-B604-688D78D9A0C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ca803d15ff0c07b633015a8b6e798245a6d0a86","datavalue":{"value":{"entity-type":"item","numeric-id":3519501,"id":"Q3519501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$233C1826-467C-4EED-A215-821FA71470BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b341170915b21d1e07bc777ecc1021ee4d6bc57b","datavalue":{"value":{"entity-type":"item","numeric-id":3578192,"id":"Q3578192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$83B10842-5A8C-4278-BE1D-0CDD380B76EF","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":"Q6119674$8C9941F1-9D1D-4040-AF33-E312F1C110AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17d805b01b31fa9a707e4c2d8061776d6d2c3fb1","datavalue":{"value":{"entity-type":"item","numeric-id":840700,"id":"Q840700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$EC0468AB-5267-40D5-9C75-8676863B51AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c297d02e2e54517f82bd75fe7cd937471e1f867","datavalue":{"value":{"entity-type":"item","numeric-id":5212801,"id":"Q5212801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$BD4B39CC-048C-4845-9282-4589F7269C7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa5b2f702f7f5e404867b16c0c8ee65c5bc19618","datavalue":{"value":{"entity-type":"item","numeric-id":4608006,"id":"Q4608006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$4093812F-EC4A-499D-B2C1-EE1A19185AD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be71f694d3c487d6769b93eadba1025f61d88e77","datavalue":{"value":{"entity-type":"item","numeric-id":5212802,"id":"Q5212802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$E18B4BD6-6455-49CA-92EB-AAC260941677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47da270d6573f7b550022bf493ad6c2294e41557","datavalue":{"value":{"entity-type":"item","numeric-id":5111241,"id":"Q5111241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$091FA9AA-C583-4F6E-980D-599DD6A9BC65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c97bea8313302d4aba346d0ce40d208fb04754b9","datavalue":{"value":{"entity-type":"item","numeric-id":3532582,"id":"Q3532582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$DEA08510-A313-4B39-82D1-E28946CF3B53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea5c9eccb9ad7e55410d02e1bab91d3b286f2caa","datavalue":{"value":{"entity-type":"item","numeric-id":2897943,"id":"Q2897943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$391BCFF3-4CA9-4260-BB15-981639D4E4F2","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":"Q6119674$5513187A-8753-4EB0-A187-8355B409E957","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebb36e514d5ce98d1e37b475a3a6456da304d689","datavalue":{"value":{"entity-type":"item","numeric-id":3540174,"id":"Q3540174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$1CBCACD0-29BD-47B3-AD31-2411617BA2F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7aaa9bb137fa2b1d06177861fbdb923853dbb86","datavalue":{"value":{"entity-type":"item","numeric-id":5248532,"id":"Q5248532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$F216A9B3-EB09-4900-9842-1CFB32DCAAF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5c6061c3f6daf7454d0e9c58daef6f441530aa","datavalue":{"value":{"entity-type":"item","numeric-id":4210136,"id":"Q4210136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$1328A91D-08A0-4EE4-863E-27176247B0EE","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":"Q6119674$D62BD0CE-F80F-428D-BB4F-1301C413D2A6","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":"Q6119674$0C5BBF16-F7E9-488A-AC9D-CEA0B77BE796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19a62d39b10622749e338de38252fcaed5d04493","datavalue":{"value":{"entity-type":"item","numeric-id":1276253,"id":"Q1276253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$2A9706D7-3F57-4301-BA9A-0374A1CD2CA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce20482255e0cc12b9b9d67540465d5e845e2b52","datavalue":{"value":{"entity-type":"item","numeric-id":1274280,"id":"Q1274280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$883AC105-567A-4DD3-AF13-84400FEAF85E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"683eeeac3d2109cb22e369dffefc9ceb3f986756","datavalue":{"value":{"entity-type":"item","numeric-id":4993605,"id":"Q4993605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$94A786FB-6B9F-46C9-A5EA-DA7C037CBDEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee0d67e60e0b10b9a6a749cf847e30457c2c3994","datavalue":{"value":{"entity-type":"item","numeric-id":2259853,"id":"Q2259853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$837DEE4D-0455-4B62-8B64-2B4E4D5DC713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ae41416b3c63fb62fa987b6d8dfe2556eabf311","datavalue":{"value":{"entity-type":"item","numeric-id":5845380,"id":"Q5845380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$48E78290-1D45-4DB2-B859-3495F826405A","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":"Q6119674$26E5CB87-E759-4C70-89EF-6F98517E2516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efa0db5c3adaf969c82b8cc399697a5c12ecf7bd","datavalue":{"value":{"entity-type":"item","numeric-id":5111286,"id":"Q5111286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$95EE23AD-638D-4E20-A587-2F4A1A9B75F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31b53e1ffc7cdd11df2d0a7596345d776fe53b3f","datavalue":{"value":{"entity-type":"item","numeric-id":2318479,"id":"Q2318479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$C714868A-54E5-4C0F-995E-360DB4D918C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbf845399cfc2fa36cc448865f810566596b9d10","datavalue":{"value":{"entity-type":"item","numeric-id":5133982,"id":"Q5133982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$049BA9D2-2CE5-4B7A-B9ED-9D0ADE3436D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53486be175772fcc7c23be1a63c774bd6bb07da5","datavalue":{"value":{"entity-type":"item","numeric-id":5863609,"id":"Q5863609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$17BE86C1-2D4A-4ECD-8C92-62051E913A50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"638b709beae6c860c43e18e0709e86bdcbe2b081","datavalue":{"value":{"entity-type":"item","numeric-id":5144900,"id":"Q5144900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$BEDD1257-EB0E-4C65-B568-85FCD6713B54","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"769cc5afef513b6341587ec84cf2c82c9e47c04a","datavalue":{"value":"10.4171/ICM2022/125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6119674$04063EC9-C75E-4E32-9C26-6E8296DE0CD3","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6119674$424ADA48-4714-44E2-A483-43D1FFF60661","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6119674","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6119674"}}}}}