{"entities":{"Q2277848":{"pageid":2288591,"ns":120,"title":"Item:Q2277848","lastrevid":49489348,"modified":"2026-01-07T07:14:51Z","type":"item","id":"Q2277848","labels":{"en":{"language":"en","value":"Counting the number of solutions for instances of satisfiability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4197418"}},"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":"Q2277848$0047C9ED-C762-483D-A837-1F225AFAA399","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"77d98d8b959f1bf71286bc70978d5e82f3f9625b","datavalue":{"value":{"text":"Counting the number of solutions for instances of satisfiability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2277848$A2D562EC-A19B-4F39-B15E-61ECCA972672","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8827578183cff9ce865892fabeeec0a9cf7e2574","datavalue":{"value":"0725.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277848$292A123B-EC33-4F5A-B953-AA7F3091FC43","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1ef2e289e9655c5a5dfbdc0f59c03d9a52c71a22","datavalue":{"value":"10.1016/0304-3975(91)90315-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277848$605A0F0C-77A3-4C3D-9B28-FE6C2FD58504","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bfae979f0a47bfa42d8c494b5d7ad537e92bd6b4","datavalue":{"value":{"entity-type":"item","numeric-id":808704,"id":"Q808704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277848$CC526C56-A987-487B-8563-62EB6AC89F05","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":"Q2277848$9FC32832-092B-4CDD-AB86-27EF5B88935F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q2277848$927CC534-A5DD-4487-857B-3B87E75F50FC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"056c1ec9681523ed92e0486551a207ce62b6343a","datavalue":{"value":"We attempt to count the number of solutions of SAT instances by combinatorial formulas. For this a notion of independence between clauses is introduced. A formula for computing the number of solutions of independent clauses in linear time is given. We establish a formula for computing the number of solutions of a set of any clauses. Transformation of a set of any clauses into an equivalent set of independent clauses is proposed. The transformation allows all solutions of a SAT instance to be determined with a time complexity less than \\(L2^ n\\) (L being the length of the instance), i.e. \\(O(kr_{\\max}2^{r_{\\max}}\\alpha^ n_{r_{\\max}})\\), n being the numbers of variables, k the number of clauses and \\(r_{\\max}\\) the maximum length of clauses (for example for 3-SAT \\(\\alpha_ 3\\approx 1.84)\\). Finally, experimental results are provided for variations of number of solutions by number of clauses for random 2-SAT and 3-SAT instances. These experimental results are in agreement with the theoretical results established in \\textit{O. Dubois} and \\textit{J. Carlier} [Probabilistic approach to the satisfiability problem, Theor. Comput. Sci. 81, 65-76 (1991)] concerning the mathematical expectation of the number of solutions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277848$568B3733-A9A8-40E1-9A39-AB67F59A64CD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277848$4EE8D7FD-E892-42F9-93B8-0FEC7AC86920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277848$B6EA80B6-C336-420F-9FBA-CC54BDEF21D5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"884649bb67ce3cb97194747c615a73b109bd70f1","datavalue":{"value":"4197418","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277848$7C890961-29FC-4E94-A0F9-1223E4B09D0F","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":"Q2277848$F37CEBD5-23BE-4D3F-BDDD-2D3851D516C7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c317ee9b89d25866849eff84487be5a7c7991b60","datavalue":{"value":{"entity-type":"item","numeric-id":3331209,"id":"Q3331209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277848$7DD4BBA6-5A10-4C79-8EE6-E548772CE70A","rank":"normal"},{"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":"Q2277848$130716AC-A208-465D-9343-0709B65D1F6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"230d404ddf32749cc3483b594ad900fe804704d0","datavalue":{"value":{"entity-type":"item","numeric-id":1822964,"id":"Q1822964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277848$0A1489E9-23EF-47DB-A9AE-898E973A3EFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8410640d25d556d9604468897a194369fdc3a7e0","datavalue":{"value":{"entity-type":"item","numeric-id":808705,"id":"Q808705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277848$D24B2756-2873-4ECF-B0CF-3A4E56FA27F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277848$1C3901B1-A2AD-484F-937C-202A24814C48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277848$7C501295-A2A7-4B0A-B4D2-64403C32C1E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c05666343bfd0892ca2f08d23cb08dec3f97399d","datavalue":{"value":{"entity-type":"item","numeric-id":1070255,"id":"Q1070255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277848$FA477004-FC41-4DF4-8370-842571456813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d50041fd827b9a880db5475227f379529c471731","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277848$2B693A2F-B4DB-4F0C-9C8F-66BADF930013","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":"Q2277848$2711F9D2-9203-42F0-AECF-BDF7D600DDE1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"342abf226e3781e2afcd4a8277db00937b3b058c","datavalue":{"value":{"entity-type":"item","numeric-id":672138,"id":"Q672138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f9fd3c0ba7ce8ffa59320f15559d70cd9ffecb6","datavalue":{"value":{"amount":"+0.8304308652877808","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":"Q2277848$BA082E31-2372-4A58-8892-0388EF634BD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e764e3d1332b136924b1d17cbe317eb3813977a","datavalue":{"value":{"entity-type":"item","numeric-id":2309479,"id":"Q2309479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f9fd3c0ba7ce8ffa59320f15559d70cd9ffecb6","datavalue":{"value":{"amount":"+0.8304308652877808","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":"Q2277848$35C51A34-F5C8-4568-AD4D-9F0EEF5C2213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85307005f9aa7b14e41627295230e50fdc5b2df7","datavalue":{"value":{"entity-type":"item","numeric-id":4808676,"id":"Q4808676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf38ab8ae9954f51448b98dedfa89ebc30aa5d42","datavalue":{"value":{"amount":"+0.8250274658203125","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":"Q2277848$551434EB-97B6-4026-8202-0408DA6D147A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"481ba62f2326cf0138f169b1c2bc980f74461d51","datavalue":{"value":{"entity-type":"item","numeric-id":4475696,"id":"Q4475696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72d32f8900084453af72bb99c42b01006fc549c9","datavalue":{"value":{"amount":"+0.8091205358505249","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":"Q2277848$59B4EFD4-E311-4D2E-B29D-0DE1143B0EB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e538b655714f5962a68723c41859f66c7436fa9","datavalue":{"value":{"entity-type":"item","numeric-id":1770390,"id":"Q1770390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"476ca4e62f3c756790a3d7f0cf84ba8741e1c96f","datavalue":{"value":{"amount":"+0.806215763092041","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":"Q2277848$1599A59C-99AE-4B93-9A82-AF493FC0DAD2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2277848","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2277848"}}}}}