{"entities":{"Q862399":{"pageid":864247,"ns":120,"title":"Item:Q862399","lastrevid":64939011,"modified":"2026-04-11T23:14:06Z","type":"item","id":"Q862399","labels":{"en":{"language":"en","value":"Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5118122"}},"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":"Q862399$19426A8C-075D-4222-B66E-DF45B161D39A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4d5b04536bb1f3e0bd2365e9d17a4e7cbcbe2083","datavalue":{"value":{"text":"Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q862399$3332B6B8-DFD2-421F-9AFC-86EBF22EC0AA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"04f8c82145b070815fcd1f0bd5d4d6f5a115ff09","datavalue":{"value":"1109.68098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862399$24DBD278-AC60-401D-BBAB-1C2352EC21F5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dda6b61323c36da4336c78f2a00f81b412a8cdcd","datavalue":{"value":{"entity-type":"item","numeric-id":430822,"id":"Q430822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$E81C87E2-D8A6-4D4E-A3EF-1A154F4DB507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c9dd58384b41cd0e0a1a2a3006084e0e7c07e0e8","datavalue":{"value":{"entity-type":"item","numeric-id":413275,"id":"Q413275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$7F83307E-8103-49B8-839F-A1A2A2861A89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"082fc9f964d52bb224385bf2fb43b8343199b054","datavalue":{"value":{"entity-type":"item","numeric-id":234710,"id":"Q234710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$09BE3CF7-126C-4F98-8F11-3F48A16ACBA5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b84cc8b5923f45dc86ae69f67f68bf56d7ecfce9","datavalue":{"value":{"entity-type":"item","numeric-id":174771,"id":"Q174771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$8274DC40-C701-423A-8E8A-B366B81F2D05","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b780548d1931bae4ac5b1caff374698a268a9351","datavalue":{"value":{"time":"+2007-01-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":"Q862399$F5617173-7F15-4653-BA56-54DD3CC6F698","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862399$4BBA0C18-6AE6-4FCA-B206-1D03E9CCD513","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b8c8fd629d6b8a9676bf2f94bf048c08f35feb97","datavalue":{"value":"5118122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862399$4E8100BC-BFE9-4ED2-8831-E86A4D881C42","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5377518a4a44721a3325809cb7ef2475652a590a","datavalue":{"value":"contemporary algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q862399$71931963-3C5E-4BB6-B44D-5ED1E858A72F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c4628391bc7e2f29119ced30c12a75c601307e8","datavalue":{"value":"propositional satisfiability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q862399$38DD0EB5-EBA6-4632-AD38-8E2666106A12","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":"Q862399$5228B8E4-96CE-405A-BA49-5240C36BB058","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ba46f3450e6b71f4993e015071811ef0a79afe47","datavalue":{"value":"https://doi.org/10.1007/s10817-005-9006-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q862399$64104C62-F6BC-4879-86E5-3025ED91B009","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dfc97f3576711cfc682cbb690e7f2de02b768271","datavalue":{"value":"W2149719182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862399$90B19CDF-AB94-46D2-84F4-D6D4E6016C9D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb9ec8e1184e554325a121c8e693cdabd0b731eb","datavalue":{"value":{"entity-type":"item","numeric-id":5175988,"id":"Q5175988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$A1263762-8E5D-4AF0-B6FB-A66E8B5E759B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15a144fb2868c504ec25b6976179a5c49a779f8e","datavalue":{"value":{"entity-type":"item","numeric-id":5501251,"id":"Q5501251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$E08FC3F2-F64C-4446-8E24-90AC418BCD6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a50fc703a31d5ca8bf26610084321c6a9db1d62","datavalue":{"value":{"entity-type":"item","numeric-id":5422485,"id":"Q5422485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$05FDE6D5-D23B-431F-835E-018A5AB7D719","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50621bbf1c084d93515abb8fb9d0b9bcc1e49ecb","datavalue":{"value":{"entity-type":"item","numeric-id":4651526,"id":"Q4651526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$D2B328A3-512C-4EED-A6F0-BCA51EA67ED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3df499f57db6ea2558ea92ba2027ece7930c8d74","datavalue":{"value":{"entity-type":"item","numeric-id":430838,"id":"Q430838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$055A0DCA-3EFF-428D-848F-22371144F82C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d503877c102eb525b85b566e37d6aac70c467a4","datavalue":{"value":{"entity-type":"item","numeric-id":1432645,"id":"Q1432645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$1BAC543C-6182-4308-99BC-1ACA80D2D17A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08b529296035947435eb136154e374f9657d895b","datavalue":{"value":{"entity-type":"item","numeric-id":4406287,"id":"Q4406287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$EB344201-2EC3-4A14-AE06-412E1F782361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62cff4d07ffcb71b5bb9f399ad2347b51931f095","datavalue":{"value":{"entity-type":"item","numeric-id":5621961,"id":"Q5621961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$6EE84A13-1DAF-4F6A-A9E0-DCAC2EE1EBEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c0e6b90c16ae5fa1eac19212a306cb84ffec72b","datavalue":{"value":{"entity-type":"item","numeric-id":5613969,"id":"Q5613969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$0FD8B147-2EDE-44FD-98BB-62897D5D2BEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1883abac9be31059cdfe4cfbd5eb3c92cfdc0e52","datavalue":{"value":{"entity-type":"item","numeric-id":1977754,"id":"Q1977754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$E276371D-D0CD-429C-ACBF-FAD3B48E608B","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":"Q862399$02550CA5-D3BD-485A-B13B-302A253D64A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d403173afb7946dd1519a703cb655d48198f8563","datavalue":{"value":{"entity-type":"item","numeric-id":4952609,"id":"Q4952609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862399$FF1ACD3B-657A-4E54-9DF8-27A635BA7FA7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"189c274bf7a452535b3ae587b8d09f35c1c9af64","datavalue":{"value":"10.1007/S10817-005-9006-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862399$51C56393-37DF-4CEF-AADD-BA37E63E3A93","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e1f4345d84abcd2f8502e6a44a0a7defbfeb5c6","datavalue":{"value":{"entity-type":"item","numeric-id":5466449,"id":"Q5466449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ced37223db076745286447b7c9826e50dbf11b7e","datavalue":{"value":{"amount":"+0.9926490783691406","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":"Q862399$DBEF529E-B60C-4945-A073-D76FC972E5BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54ff441d5f90660fe62074e8e4e7c125ba1ffa58","datavalue":{"value":{"entity-type":"item","numeric-id":2843337,"id":"Q2843337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d1541b7c2755f7a18909926c2a091c1de129cba","datavalue":{"value":{"amount":"+0.902643084526062","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":"Q862399$D7AB8814-A64B-4B75-AD02-1B72DF1197F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"796cfe4f2037e0da912a5d28a214e6134546e923","datavalue":{"value":{"entity-type":"item","numeric-id":3104641,"id":"Q3104641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f30269f483292a27a0a50e52e288dd771f3338c8","datavalue":{"value":{"amount":"+0.8768424391746521","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":"Q862399$BBA605BF-91E2-49A2-989D-DC87865D13D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c09c3fd3e24d2a849d90e42d6bd2de2e95bd73a5","datavalue":{"value":{"entity-type":"item","numeric-id":5501251,"id":"Q5501251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1efe9e419dcecfbe3d16910692089d1688e5d2b9","datavalue":{"value":{"amount":"+0.8630138039588928","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":"Q862399$AC8AB835-A854-4B3C-82F3-0C7C4369189A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb65919fc597229a6a39b39e1b70a0498b02ec41","datavalue":{"value":{"entity-type":"item","numeric-id":2577593,"id":"Q2577593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11758b2f469a073e1dee59c868bdb81c48c86af5","datavalue":{"value":{"amount":"+0.8611270189285278","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":"Q862399$D657049F-6ADC-4E75-BB7F-08F732A28F4F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Exponential_lower_bounds_for_the_running_time_of_DPLL_algorithms_on_satisfiable_formulas"}}}}}