{"entities":{"Q1082830":{"pageid":1093582,"ns":120,"title":"Item:Q1082830","lastrevid":48987181,"modified":"2026-01-06T10:07:45Z","type":"item","id":"Q1082830","labels":{"en":{"language":"en","value":"Solving satisfiability in less than \\(2^ n\\) steps"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3974341"}},"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":"Q1082830$143FE0B3-5707-44ED-BB9C-1E4C62E13B2D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4c4ad96838bcfda460a24d361bb238c932c71742","datavalue":{"value":{"text":"Solving satisfiability in less than \\(2^ n\\) steps","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1082830$85646F65-55D9-45A4-A7A4-E783A1E4EC95","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2382628665f2b13cff99596462d95c273a0facdf","datavalue":{"value":"0603.68092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082830$D7FFFE21-723E-4E8E-8726-0FE333409937","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"afe44f71adee841800c47f42a00174af0f2c270e","datavalue":{"value":"10.1016/0166-218X(85)90050-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082830$BD91AAB3-333E-4FCE-B682-3B5C6EEE44D4","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":"Q1082830$7049F866-546C-4EE2-A698-1240348740A3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1082830$48C4D58C-C408-49C0-BF6B-40AAC9128125","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a00a3c9e69614df87dd17873b36478f4ec75b7e2","datavalue":{"value":"In this paper we describe and analyze an algorithm for solving the satisfiability problem. If E is a boolean formula in conjunctive normal form with n variables and r clauses, then we will show that this algorithm solves the satisfiability problem for formulas with at most k literals per clause in time \\(O(| F| \\cdot a^ n_ k)\\), where \\(a_ k\\) is the greatest number satisfying \\(a_ k=2-1/a_ k^{k-1}\\) (in the case of 3-satisfiability \\(a_ 3=1,6181)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082830$58D6BFC3-3296-4D60-95A4-036B5B425137","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082830$DD8A9597-C2A1-4184-93B3-52B552D37C01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082830$28D52C69-E6FB-4C1C-856E-9B422CD6A191","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a139cf4a8d65af4d16f59eadc4389e31df78e18","datavalue":{"value":"3974341","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082830$033B4AA4-8EFE-4313-A287-02B486E01AE2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082830$E090AE54-F86D-4B85-A685-A122178C1BBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e9f478cf938bffe63079a8138ad391530bbfff8","datavalue":{"value":"boolean formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082830$10564162-BC87-4781-BACB-3F32344FCC5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"828e479c39c5c64293eb95e0403dbef7bbf79066","datavalue":{"value":"conjunctive normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082830$1D9103B6-2388-4C63-B86A-A30058096C7A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b9f391e6322208fe1ff9282b50ef9e948c0574c","datavalue":{"value":{"entity-type":"item","numeric-id":284584,"id":"Q284584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082830$F37BD045-F983-46A2-9460-B2585ED93D95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a52c13955159b7796643777df723759736e16f2","datavalue":{"value":{"entity-type":"item","numeric-id":714018,"id":"Q714018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082830$38B53446-5FCA-4325-AC6F-FD49BBB3B35A","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":"Q1082830$970199D5-20A9-43A9-B96C-3A2D475D5EBF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef757ecac8e00102e8fe2d81d7657ee3391ff698","datavalue":{"value":{"entity-type":"item","numeric-id":4138187,"id":"Q4138187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082830$C5188F5E-29C2-4D57-8D36-74BBBDEEF337","rank":"normal"},{"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":"Q1082830$2115D8B0-F0D7-4512-9F45-BA7058CE0A18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"789c9b261b79882661741dd01add5c380b8a4ed3","datavalue":{"value":{"entity-type":"item","numeric-id":787685,"id":"Q787685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082830$AB8E66CD-5287-4A20-98BF-6CAC3E28B958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01f475f67857ea5c99b966d364e267a1b4d9657a","datavalue":{"value":{"entity-type":"item","numeric-id":4159059,"id":"Q4159059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082830$758ACB7C-DCDF-4C8B-98D6-BEEA2B497E7F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f68dd49e8d790217f4c6e141204af1920c329f5f","datavalue":{"value":{"entity-type":"item","numeric-id":4283247,"id":"Q4283247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"541151f2f12b50881bc2032c5e971e5e80b5f848","datavalue":{"value":{"amount":"+0.9553661346435548","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":"Q1082830$0B1CEC32-8543-40B0-A2C2-2412A9298034","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d61d84e070a214db063b64febdc62a5edfe35cdd","datavalue":{"value":{"entity-type":"item","numeric-id":4218095,"id":"Q4218095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05501a9c7179c29b8a00ca6ee763157096efab3e","datavalue":{"value":{"amount":"+0.9511088132858276","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":"Q1082830$1EF4573E-1DCC-4A20-B511-8738266B82E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"651006af4f64a7c4bbcbdf5718f802833b4f6a47","datavalue":{"value":{"entity-type":"item","numeric-id":4651809,"id":"Q4651809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86ad8626c1c9e748b9ce00632daba9092dd7d7d1","datavalue":{"value":{"amount":"+0.8852740526199341","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":"Q1082830$C131A2E9-36CC-45BF-AE06-004281BA8A30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7c44f22df52e492976713f563fde4e11d159f1b","datavalue":{"value":{"entity-type":"item","numeric-id":1115189,"id":"Q1115189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d48eefd5f50e8352261d8b3ff0df279b108e7471","datavalue":{"value":{"amount":"+0.8586915731430054","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":"Q1082830$7AE6F8C3-A626-44AC-9877-C9273FEF4CF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa95e22327925cc9f6612512d3bc9000bebc1e49","datavalue":{"value":{"entity-type":"item","numeric-id":1964360,"id":"Q1964360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18530b07371d40540bfd922eb0174f4964b6a227","datavalue":{"value":{"amount":"+0.8483923673629761","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":"Q1082830$0DFCA8B2-4E0B-4A05-BA80-231121615E1B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1082830","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1082830"}}}}}