{"entities":{"Q284575":{"pageid":286342,"ns":120,"title":"Item:Q284575","lastrevid":60692229,"modified":"2026-04-10T18:33:20Z","type":"item","id":"Q284575","labels":{"en":{"language":"en","value":"The complexity of counting locally maximal satisfying assignments of Boolean CSPs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6581634"}},"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":"Q284575$322AE53B-D092-4BBB-A388-C5D7BB4542A9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2182f4978ed21957fd942f4d06fe2a764c26f5a5","datavalue":{"value":{"text":"The complexity of counting locally maximal satisfying assignments of Boolean CSPs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q284575$1D6EB584-D63A-4FAC-A888-F96AD59B70DB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"44dbe0b5370d60b0faffebe5dbfa10ae91b5cf00","datavalue":{"value":"1339.68117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q284575$E28B968C-0B19-49F1-A984-A395F3BD586A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad508c4cfc8fff336ea19a6d0a5b336b7e224f18","datavalue":{"value":{"entity-type":"item","numeric-id":242858,"id":"Q242858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$E42E68FF-1596-493F-8BFF-A7857798B2F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"871bc74022ea4f6f28f92d19fa6227a3c4413324","datavalue":{"value":{"entity-type":"item","numeric-id":1058289,"id":"Q1058289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$58D95E7D-527B-4FB6-9E05-423C5B3B8F32","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$DA60B5E3-B006-473E-AF3A-965060140D6F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"520e6f0241f1a69086f50367d5722006ec0b624b","datavalue":{"value":{"time":"+2016-05-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":"Q284575$EDDB3357-F845-48D6-B61A-6A2D7DBDC56F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d42bdd01115313ba75ea8588086727a6e1f82330","datavalue":{"value":"https://arxiv.org/abs/1509.03543","type":"string"},"datatype":"url"},"type":"statement","id":"Q284575$109CAF42-C8D4-4322-BA27-C3D8CE4E1116","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q284575$ADB71B85-9FE2-40AC-A7EF-5D018C183FC0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a4c78e66098504874281145a7e73d9270901096","datavalue":{"value":"6581634","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q284575$3183717E-07A6-47E0-A506-2BC95EE1DBFC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a348f9efcaabdd35d491583f05dde8d8e0eb673","datavalue":{"value":"constraint satisfaction problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q284575$A96015E3-965A-41F2-A2B7-A6E6463BAF97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c8b0401e4d3bf1ebf10087d4c89022cf0a5b1f8","datavalue":{"value":"computational complexity of counting problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q284575$B0C3EA6A-53A3-4C0B-BCB3-5F54BDFD4DF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b735fd1f84caba3f2ebe9dc55af320c6e7ec05b8","datavalue":{"value":"approximate computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q284575$BAD8E4EF-6AF7-4E46-9253-39A2EB564A1D","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":"Q284575$3B795410-51D1-4769-8F1B-2D56DBCB25F2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dbc6c3e4fc1e795179f63b85bc0eb7744e073fb9","datavalue":{"value":"W2331597986","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q284575$C737726E-DE47-4F7B-B476-36ABFD1F6FA2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"927b3bb72268e811f46476ea8559c6205f6bc0d0","datavalue":{"value":{"entity-type":"item","numeric-id":1917076,"id":"Q1917076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$C4BF7FA8-B1DB-439F-A707-97EA69E72DE9","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":"Q284575$37D9A453-AE3A-4FC1-9096-3A05BFC78C85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46d9571fba27d91274408c6b1abd2f3213070da7","datavalue":{"value":{"entity-type":"item","numeric-id":955340,"id":"Q955340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$DDEA6119-33C1-46A1-8F64-58D93CF19DB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c67621df0c174facf94484077bda2f7f5ed54b66","datavalue":{"value":{"entity-type":"item","numeric-id":963360,"id":"Q963360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$CFF967B8-32CC-457B-BA0E-AE85EE871C3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71c1c8187359268cad650520f7a768093722908f","datavalue":{"value":{"entity-type":"item","numeric-id":2566034,"id":"Q2566034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$2DCE2A62-A4FC-4AED-962D-F442A3A9E6DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bdfbfd559e71543d5cb50c83fc21e3ae2fa71a1","datavalue":{"value":{"entity-type":"item","numeric-id":1879247,"id":"Q1879247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$DD49244F-616E-4413-A27E-DD4920D3FECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57bda985c0169b6522b9f81e020ba310f47e98b7","datavalue":{"value":{"entity-type":"item","numeric-id":972385,"id":"Q972385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$AC2F48D2-36B4-4BE0-B028-684356C9C45B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb85ce0c9955a87b25eb762617c3c81fa20b106e","datavalue":{"value":{"entity-type":"item","numeric-id":3448823,"id":"Q3448823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$E51DC42B-77BD-4516-9F0E-C7415DF21200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34e1f192637186c0427cfb736df07ca51f7d1e45","datavalue":{"value":{"entity-type":"item","numeric-id":837174,"id":"Q837174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$E55ABC3F-7571-48AC-B4B3-9BFCC502F5AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"302adbaf2b8357f20069be2a0dab5e3eb2168585","datavalue":{"value":{"entity-type":"item","numeric-id":1109573,"id":"Q1109573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$AFF344A0-D62F-4187-9AC0-A6B6697B65AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82ba3bd74ef41e0757015be3b53bca7ad9cb71ba","datavalue":{"value":{"entity-type":"item","numeric-id":5463630,"id":"Q5463630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$164836F9-2961-42C2-B12A-56363E1DE85D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3798f797f1d96df74883f771f001f3f714b860f0","datavalue":{"value":{"entity-type":"item","numeric-id":3036719,"id":"Q3036719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$90656DD3-C35D-4A3B-9FD3-7228A62F1161","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":"Q284575$C9AB5AE6-3D2E-4D47-854C-718F66CA7187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b71c369fb8d3c656ece2d0814dcb2ca79a02975","datavalue":{"value":{"entity-type":"item","numeric-id":1193633,"id":"Q1193633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$C528AF46-738E-441A-B045-EE80BA462001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c516460706e34bfacf776c096f40a576fd2116","datavalue":{"value":{"entity-type":"item","numeric-id":600247,"id":"Q600247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$6FBEF83F-3FA6-48CF-995F-4A1AB8CAEE74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70536879af054717c0f3d9d913a10e93c328980d","datavalue":{"value":{"entity-type":"item","numeric-id":3853129,"id":"Q3853129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284575$7C54C7FD-83D4-46F8-98A5-9FE0672F86FD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"81a1a82269d06264915c0cebc00c0eaa3a29fbbb","datavalue":{"value":"10.1016/J.TCS.2016.04.008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q284575$BC43167E-B4E8-457F-993B-283CC27F8146","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abef8aa872381c4e4d1badeea4396cb63c08c1c2","datavalue":{"value":{"entity-type":"item","numeric-id":1777392,"id":"Q1777392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4e6bda9e3c3710ca11dcbb6b17d21533e9d1cdb","datavalue":{"value":{"amount":"+0.9125012","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":"Q284575$936512FD-F6F0-40BE-84D2-78F8364A077C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcc42efa76402e6f26f0ceb0aca84bc5ca4e493e","datavalue":{"value":{"entity-type":"item","numeric-id":5395730,"id":"Q5395730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebf7f4253763627e8a895397d903a36c5e58dff8","datavalue":{"value":{"amount":"+0.89622724","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":"Q284575$DCC6E5FC-85E3-434B-8547-F8CD8130D279","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2977f2bbdc41f1d7cbad463f769cbc9e3946a5e8","datavalue":{"value":{"entity-type":"item","numeric-id":3521956,"id":"Q3521956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebf7f4253763627e8a895397d903a36c5e58dff8","datavalue":{"value":{"amount":"+0.89622724","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":"Q284575$2837E885-7F0E-43E4-913A-B53A82509AC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"715f63411a3720597a877e67d9ef2d508e7e40f2","datavalue":{"value":{"entity-type":"item","numeric-id":3576757,"id":"Q3576757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc866090b212f19b1f81084a4f2f880401277b94","datavalue":{"value":{"amount":"+0.8938811","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":"Q284575$D26E30E3-334D-40BF-8E38-047F5FBACB3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92f86d85a1b0a06ff24416d277336ec20fe2b063","datavalue":{"value":{"entity-type":"item","numeric-id":3565118,"id":"Q3565118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f28d6af875a4481ff769ace99467db197226a1df","datavalue":{"value":{"amount":"+0.89100933","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":"Q284575$8285D7FB-7506-4EDD-B5ED-CD8E619462AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f28a758183f8163346f74829d2d795d44fbe92f9","datavalue":{"value":{"entity-type":"item","numeric-id":443724,"id":"Q443724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e380d6cb072a03af0c1ce712f8afb586f3257f19","datavalue":{"value":{"amount":"+0.88723373","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":"Q284575$F79F22F2-4A01-4744-80A7-5BD028C1312C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38d14b69617873c5f577b30f05bd43a6502b83bd","datavalue":{"value":{"entity-type":"item","numeric-id":2957879,"id":"Q2957879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f558d089a29bc5e19a92a6526b270e5815a12322","datavalue":{"value":{"amount":"+0.884611","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":"Q284575$EDC23586-348E-41FE-B4A0-CCBC2826A097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18055d416233cd381b4a771d081db92424ed9ae3","datavalue":{"value":{"entity-type":"item","numeric-id":743130,"id":"Q743130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f558d089a29bc5e19a92a6526b270e5815a12322","datavalue":{"value":{"amount":"+0.884611","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":"Q284575$A1EF71AC-BCE0-452E-A68E-015DEE9F5127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7ecd180d3ecfe2479f28bacb1691fc838b4b97e","datavalue":{"value":{"entity-type":"item","numeric-id":1917076,"id":"Q1917076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea079b10ea4375d21139c7c5ddd582a83cc49d8b","datavalue":{"value":{"amount":"+0.8831432","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":"Q284575$48860ED5-6D98-4495-9114-78365466C642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40b15d932f7a272848e7e302952894d9897e4c93","datavalue":{"value":{"entity-type":"item","numeric-id":3066165,"id":"Q3066165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14a57180fc242bdcdd45badcc1944a4dbabee268","datavalue":{"value":{"amount":"+0.88166153","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":"Q284575$ED0FDA0C-66F2-4DCB-912D-621EFD43BEE9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of counting locally maximal satisfying assignments of Boolean CSPs","badges":[]}}}}}