{"entities":{"Q1822244":{"pageid":1832986,"ns":120,"title":"Item:Q1822244","lastrevid":73448886,"modified":"2026-04-14T16:02:15Z","type":"item","id":"Q1822244","labels":{"en":{"language":"en","value":"Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem''"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4001483"}},"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":"Q1822244$09FA06CE-6DFF-4E9B-ADCB-B0AFD61F4DD8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e1adae5bd5070ec5aa3e09da2ec1d685c8644bce","datavalue":{"value":{"text":"Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem''","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1822244$923D8909-8B36-4DEA-8922-CF77DE262347","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3f09fcc196c4dc4da1fcaff9174e2c1871902b4f","datavalue":{"value":"0617.68046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822244$7A4F5E04-6E09-4203-AA34-2938BE6306F1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f29ac1167e1fa1c5d0d4681dd52dd0b0ea5a3320","datavalue":{"value":"10.1016/0166-218X(87)90032-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822244$948CCE39-A1EF-49A2-9BE3-9A84D67F0AB9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"28bbcc74fcb402af071729d124478254f15cbdb4","datavalue":{"value":{"entity-type":"item","numeric-id":584253,"id":"Q584253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822244$375DB8D9-A6EA-4FD4-BDBC-4DDDC0B250C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb85fd2c1ce489cbecf5dc649288fae9b7018a3f","datavalue":{"value":{"entity-type":"item","numeric-id":673601,"id":"Q673601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822244$27E5A493-7E2D-4015-B40B-8975D462E809","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9878b97e16d942fa90f6e1b22b32f682f6823a6","datavalue":{"value":{"entity-type":"item","numeric-id":590477,"id":"Q590477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822244$276BBCA7-EAD4-4B41-8C39-D7E163F49DF7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822244$060BA163-5E70-411B-B7ED-D2798019F347","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1822244$839349FF-9E56-4C73-9BFC-A476FE6E08B2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"209e4cbd7e8fb7d9248fbbbb7e4a33b8a3600fa1","datavalue":{"value":"\\textit{J. Franco} and \\textit{M. Paull} [ibid. 5, 77--87 (1983; Zbl 0497.68021)] have defined a family of distributions \\(F\\) on inputs to the Davis Putnam Procedure (DPP) and then have used this to analyze a variant, DPP', which omits the pure literal rule. The main theorem asserts that for almost all inputs, DPP' requires exponential time. Although this result is correct, the proof is not. We briefly note the errors and then correct them.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822244$54E96A5B-24FD-49F9-903D-A81D63D3AB99","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822244$EBB650EE-726D-434D-8AAD-D6D18745F23D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822244$3F42BB59-B284-476F-8191-981813C95741","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f783e1e4e8265e62eb64ee9a1dae125fbb876cdf","datavalue":{"value":"4001483","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822244$D0CBA330-01B8-4F29-B2B4-05D4F462E650","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4752b484d49c9a2b93e0a9e10ae2fe7e85c97cb7","datavalue":{"value":"probabilistic analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822244$E7D4D62D-DAD9-44C7-B4A6-C6883576E76D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0b4d6e6089943a261128dec792d30fd4cdc9763","datavalue":{"value":"satisfiability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822244$1D42E149-E8AE-414D-A96D-178F4EBFFC62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91b88f4d32c7ac443b3a326e8f9fe1fc13e61351","datavalue":{"value":"instance distributions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822244$935B1128-C75D-4AB0-A34E-1D2F04AEED5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b2085f6ca6b5f22ff227aa538ed50fc77fe1a47b","datavalue":{"value":"Davis-Putnam procedure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822244$776E2932-DD8F-47B6-88EA-490D7BF7FCE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53f7a6b3529f388b241b153833f8f144a83b78bb","datavalue":{"value":"polynomial average complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822244$97B25883-3D85-4A90-A9AC-EC4AF6C38E7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822244$2260FC2F-5EAD-443D-A391-4BC9F420BFA9","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":"Q1822244$90E5669B-D142-4293-8086-2573EDED6E78","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0d47402a18255121e8b4c37559d3eb99d007b27","datavalue":{"value":{"entity-type":"item","numeric-id":1170883,"id":"Q1170883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822244$A822C4B6-7111-4A04-9299-D3ED207E643C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3006f8cf571ae9e6c7dbff78692dd2d2a7f7389d","datavalue":{"value":"https://doi.org/10.1016/0166-218x(87)90032-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1822244$7247DF2E-7916-4C61-AB03-FAC1D1C4E10A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e7e5b1b65976fe890964122e8a3f969f2e51c164","datavalue":{"value":"W2055638404","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822244$ED758052-33CF-4BEE-9E9D-364D459A2AD3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcb15256d2254f35851208fe603f797e906b9f96","datavalue":{"value":{"entity-type":"item","numeric-id":3827800,"id":"Q3827800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04b33108ce5b7bdf419a29e6f6db9a43b3786101","datavalue":{"value":{"amount":"+0.7941944599151611","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":"Q1822244$ECEBB5B4-43F6-4A88-AB1C-A7548B3F3346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8e062448ad3176ad0428cc4ca722719b43b43dc","datavalue":{"value":{"entity-type":"item","numeric-id":3694704,"id":"Q3694704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be965b3315ac918068e3297cf354ec334159d1b6","datavalue":{"value":{"amount":"+0.79374098777771","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":"Q1822244$CCFE9D09-5E2B-4874-AB16-BDF9376CE8DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"daa7bdae693216d7f67ac726ebf3ab505aaf4170","datavalue":{"value":{"entity-type":"item","numeric-id":2784492,"id":"Q2784492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eaea31ee7d49ab84540d01ed21e6cf5bf864d036","datavalue":{"value":{"amount":"+0.7863019108772278","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":"Q1822244$3DC2748C-4D9C-4A01-982A-6ED5242B83B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d9812f44016d466ef24765bb45200244fd0e3cf","datavalue":{"value":{"entity-type":"item","numeric-id":1353991,"id":"Q1353991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28b3b709bf8e3dddff7b1cf5018dccaca0014c47","datavalue":{"value":{"amount":"+0.7862317562103271","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":"Q1822244$8A029138-3F8A-4CF0-B700-950F32D53282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2142a01b3a431baa188a8311ec72749273e697e1","datavalue":{"value":{"entity-type":"item","numeric-id":3832061,"id":"Q3832061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"533d8647ebdd13aa39f6eea6fba766aafb22201e","datavalue":{"value":{"amount":"+0.7778336405754089","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":"Q1822244$D55D578C-2070-42E9-BF11-210D4133797A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem''","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Correction_to_%60%60Probabilistic_analysis_of_the_Davis_Putnam_procedure_for_solving_the_satisfiability_problem%27%27"}}}}}