{"entities":{"Q2475410":{"pageid":2486153,"ns":120,"title":"Item:Q2475410","lastrevid":50301320,"modified":"2026-01-13T19:05:21Z","type":"item","id":"Q2475410","labels":{"en":{"language":"en","value":"The complexity of Unique \\(k\\)-SAT: An isolation lemma for \\(k\\)-CNFs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5246771"}},"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":"Q2475410$229E34EC-9300-45FC-8980-3C9694D05835","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5d1f39c6aba3f4324a676380bf82fa4f8d814ccc","datavalue":{"value":{"text":"The complexity of Unique \\(k\\)-SAT: An isolation lemma for \\(k\\)-CNFs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2475410$51889B7C-A9FB-4A8B-B039-9BF9D812F4B1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3428a4ec2355c8e1ceb8df71c02b9577acf42d7f","datavalue":{"value":"1135.68020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475410$D61DE1DF-2CFA-444C-AAB9-D8E333125D31","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"089e41c8f7ccaf5215cb8d787978dedbdccbc06b","datavalue":{"value":{"entity-type":"item","numeric-id":1949745,"id":"Q1949745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$D4985397-1522-49FC-A0F0-C6D8D4528D69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afbdf0b4b75e6a0dfd1ecc76c9480c04f5fced5d","datavalue":{"value":{"entity-type":"item","numeric-id":202088,"id":"Q202088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$0CD01EBA-437F-48EE-9CC1-15DF13217C52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0d2539da0629477438d7ce1d3087216415362d1","datavalue":{"value":{"entity-type":"item","numeric-id":230568,"id":"Q230568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$97C9F90D-F7E6-4D4C-8525-3F9803F884F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d72b6c9fa09679ee04e7df5acd3659b335857c59","datavalue":{"value":{"entity-type":"item","numeric-id":192223,"id":"Q192223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$BCAF2255-AC36-49E0-AC30-C82BD8C87932","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$4BCF00FB-980A-40A2-B0B7-705BFD3EA6EA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c5191b06fb6cb88c011afaa0f154255cfe3a8de0","datavalue":{"value":{"time":"+2008-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2475410$241B8681-7FFC-4BCD-92B1-BA7E4A29BC19","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475410$6EB6F9C3-3187-409D-9F0B-BFF0076F498C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475410$278CF053-1AC6-4761-B7A7-9FDC6F2A6424","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f4881951bcb89c1e2c35fd0b65bf051a7f2c01b0","datavalue":{"value":"5246771","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475410$CD8C8B01-E0F2-400E-906A-92D2DB533B9F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2475410$C76256B9-03BD-4CF9-A49F-1586B8469CDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64b4a1c903bdbad63491df93be09359d9b4e135b","datavalue":{"value":"unique satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2475410$C056992C-6C0B-47F1-B26C-9521678695D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd35a4a55f4ef87cd1de6b19e9b8a701deb3aa69","datavalue":{"value":"\\(k\\)-SAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q2475410$54C16398-4368-4E7B-B41D-15EC93522407","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0320f86bccac5a8d4c81bf84f7aba477c80b74c8","datavalue":{"value":"subexponential time reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2475410$88354A94-AE19-4129-9654-DCEA1177D315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e89febb0bf95c87192bbbef24b8d00fe08802a6a","datavalue":{"value":"isolation lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q2475410$DFCED661-DE63-4F10-90C5-5805591E5E56","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3edd92ad3c67f5a198c15e7c3ce7d478aa6bf12c","datavalue":{"value":"Q56767456","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475410$F4B826EB-1F66-4280-96B1-6CD48FD1E650","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":"Q2475410$B96B97EC-B221-473B-B0D9-79ABC166EB8C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c4eed2e964fdd3e925dd769bbdf64d3c9847b428","datavalue":{"value":"https://doi.org/10.1016/j.jcss.2007.06.015","type":"string"},"datatype":"url"},"type":"statement","id":"Q2475410$2B18D154-3F7C-430D-A76A-7BBFCA2B12E1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"34a6ac644c50cdb67c315189fd421521d436d636","datavalue":{"value":"W2092928619","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475410$4BA081A5-E05E-4C44-A2A6-208D52FF6CCF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3417a6b158ced49b65a64b1d4cf9810c8b8be6b","datavalue":{"value":{"entity-type":"item","numeric-id":1838470,"id":"Q1838470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$1E707747-1B97-4FA4-9994-FA2FF045AE8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be6989157e41c18f8557462896243611dc2b1c55","datavalue":{"value":{"entity-type":"item","numeric-id":1853552,"id":"Q1853552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$4EB7BF60-4BA9-4A03-861B-226D5913A512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"877834c4ccddc8fbecd398cf14bee4029dffc4b0","datavalue":{"value":{"entity-type":"item","numeric-id":3434543,"id":"Q3434543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$AC8E0522-AC20-4B0E-9B87-D36D2D652EF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae35b42269b65df7a1c59338bf97c0ea301c5c81","datavalue":{"value":{"entity-type":"item","numeric-id":2488567,"id":"Q2488567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$1FCCEABD-B3EC-4A0D-81DD-86070FA44974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df874a0718fb56d6d59d535d492d255a5c0860e1","datavalue":{"value":{"entity-type":"item","numeric-id":4351797,"id":"Q4351797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$6BF59EAB-76E0-4CED-8D80-8C1AF9F30B7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a954e80b40ebc890ca3cccb9d5b9cd932f824257","datavalue":{"value":{"entity-type":"item","numeric-id":5560774,"id":"Q5560774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$F6B4FBFB-08B7-41C0-A213-66AC3450C0A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbc117c887d682c44a18cb82bd37083ff8a25e26","datavalue":{"value":{"entity-type":"item","numeric-id":4736839,"id":"Q4736839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$15717611-A07A-4E4B-A7C1-258CEBA1919D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4548ea5d583917c0fa9b6aaa6b1d48c80c1e7e","datavalue":{"value":{"entity-type":"item","numeric-id":1604206,"id":"Q1604206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$52AA6812-1742-4A1B-94BA-5483B4947EC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f84a7480c49fc409dbcbf738c5b5d98de37e02b","datavalue":{"value":{"entity-type":"item","numeric-id":5501274,"id":"Q5501274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$D0B7841F-F467-4626-9F35-472119C9205F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"633481678a0836b3846b49aa8db13fb38104e9a2","datavalue":{"value":{"entity-type":"item","numeric-id":1082830,"id":"Q1082830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$453A90C3-F786-4966-9C03-90BC433F2F57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab505d079acae70f31b63226f0d6d40ff5b0dd0","datavalue":{"value":{"entity-type":"item","numeric-id":3546306,"id":"Q3546306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$BC324372-6784-4035-AF64-F606247924ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2077fad0f8784e4f01900be189b1e93f8a2ad005","datavalue":{"value":{"entity-type":"item","numeric-id":1348911,"id":"Q1348911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$E0D10B8E-64E9-4301-8A48-876F0A9C8354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cca2e18e22bdceb10ced114e23ee143c1222e350","datavalue":{"value":{"entity-type":"item","numeric-id":4651809,"id":"Q4651809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$F7E81856-DE70-4E09-9970-C51EB34A0FB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dfd82bed9266a9eb9ee03c49c86a8c45cb2436","datavalue":{"value":{"entity-type":"item","numeric-id":1090454,"id":"Q1090454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475410$BC3323A1-D89A-44E8-BC67-8F7C77509A04","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"692ae4d665ae827bcf2d4dde5139f05ba0b5d7f2","datavalue":{"value":"10.1016/J.JCSS.2007.06.015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475410$6EF725C5-48B0-4925-8AD2-32C4F3A1235D","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"95e0f757d15eabf39494371bde1c6e65b9577c89","datavalue":{"value":"journals/jcss/CalabroIKP08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475410$98A6B5C5-E61D-4767-952E-99722442DE9B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"451fc3a6fbdfb9bbf958bb10b2350c3b5488d1c9","datavalue":{"value":{"entity-type":"item","numeric-id":3392942,"id":"Q3392942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f394a5c9757da1a6a3302a236024175131470d7","datavalue":{"value":{"amount":"+0.8362284302711487","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":"Q2475410$7A5F25AB-FD28-4B79-B666-B260F7C58D63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6456c7d409da6b9e2de61a1cd646ae0a609b5f2","datavalue":{"value":{"entity-type":"item","numeric-id":4930606,"id":"Q4930606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb649c4116b178f2b5a082e405cd10db98be2865","datavalue":{"value":{"amount":"+0.834443211555481","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":"Q2475410$D99301A6-9C6A-40CF-A520-CA252D826523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"755bb9e2da3e04a3fdd2a172851bfa20892491a7","datavalue":{"value":{"entity-type":"item","numeric-id":5943094,"id":"Q5943094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42c9109ef19849c1ad0a8aad1cfa37be4b8a5c73","datavalue":{"value":{"amount":"+0.822424054145813","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":"Q2475410$6624A871-3910-479B-AEEF-45A182FAC112","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9ddc87b56d350b2e9090d975f8e50770330b306","datavalue":{"value":{"entity-type":"item","numeric-id":2202678,"id":"Q2202678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac176d27d2efbd20bcc018274c2b05eab77340b1","datavalue":{"value":{"amount":"+0.8110150098800659","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":"Q2475410$DB01FF3C-F06C-46ED-BCA6-178D5F7B26A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26b97ba761d4e2b6ccde57061d1068fe5c8a35ef","datavalue":{"value":{"entity-type":"item","numeric-id":3440269,"id":"Q3440269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56aadf6635625c980602da36f62acb3053ff773a","datavalue":{"value":{"amount":"+0.7903751134872437","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":"Q2475410$A6314E00-EBDD-41F3-8769-79E509B6A8F5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2475410","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2475410"}}}}}