{"entities":{"Q1115189":{"pageid":1125938,"ns":120,"title":"Item:Q1115189","lastrevid":77753483,"modified":"2026-05-06T09:58:59Z","type":"item","id":"Q1115189","labels":{"en":{"language":"en","value":"Probabilistic performance of a heurisic for the satisfiability problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4085026"}},"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":"Q1115189$A76C3E46-436A-4D62-A37B-452BE4070D96","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"56c5bb85a84a3dcfc49ccac6511b20f6491f8ec1","datavalue":{"value":{"text":"Probabilistic performance of a heurisic for the satisfiability problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1115189$87B63654-E5A0-4914-B395-DA93A44A54CC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"63162f7da899bfa109d627cbde75be68caa91c88","datavalue":{"value":"0663.68059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115189$19400936-FF84-4520-8C74-9D17B7F2C268","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fff24942a372c04c58add3cb9275e41ad0ac96c7","datavalue":{"value":"10.1016/0166-218X(88)90121-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115189$D475DB6D-2CDA-4B5C-9589-02FBDA73DDE8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"59c5611d91dde001fde443243ba2b34fcb1aa773","datavalue":{"value":{"entity-type":"item","numeric-id":1115188,"id":"Q1115188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115189$6F1678C3-79EB-4330-9666-1D5CA27C939A","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":"Q1115189$D00D0BE3-58BC-4E69-9119-9FDC1328BD1E","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":"Q1115189$3232F67E-E40F-40FD-BE72-69C7E46CBAD4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1115189$04FB9520-0DCE-4B06-8412-4E1FAE9CE6F4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ad8bdb5e135fe8fec55c2d83207a6750020d276c","datavalue":{"value":"An algorithm for the satisfiability problem (SAT) is presented and its probabilistic behavior is analyzed when combined with two other algorithms studied earlier. The analysis is based on an instance distribution which is parameterized to simulate a variety of sample characteristics. The algorithm dynamically assigns values to literals appearing in a given instance until a satisfying assignment is found or the algorithm ``gives up'' without determining whether or not a solution exists. It is shown that if n clauses are constructed independently from r Boolean variables, where the probability that a variable appears in a clause as a positive literal is p and as a negative literal is p, then almost all randomly generated instances of SAT are solved in polynomial time if \\(p<0.4 \\ln (n)/r\\) or \\(p>\\ln (n)/r\\) or \\(p=c \\ln (n)/r,\\quad 0.4<c<1\\) and \\(\\lim_{n,r\\to \\infty}n^{1-c}/r^{1-\\epsilon}<\\infty\\) for any \\(\\epsilon >0\\). It is also shown that if \\(p=c \\ln (n)/r,\\quad 0.4<c<1\\) and \\(\\lim_{n,r\\to \\infty}n^{1-c}/r=\\infty\\) then almost all randomly generated instances of SAT have no solution. Thus the combined algorithm is very effective in the probabilistic sense on instances of SAT that have solutions. The combined algorithm is effective in some limited sense in verifying unsatisfiability.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115189$C6F7EB50-0EDF-41B5-A2AD-DAB20753655B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115189$2B652C77-D44D-47A2-869B-C3CF31E01DD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115189$BDA32138-C287-4E8C-98C2-13E7487AA8B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115189$C001C841-34D7-4196-895B-960661908764","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"01f2017f2c00bf498e509bbba92502d753216bf6","datavalue":{"value":"4085026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115189$03A645E7-1C2A-48AE-B98B-19212064FCDC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c17e746f34e5027fb7f45f9862bcf1e29396aaeb","datavalue":{"value":"average analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115189$71721F50-14DA-47BB-A7BE-38EF74140450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4752b484d49c9a2b93e0a9e10ae2fe7e85c97cb7","datavalue":{"value":"probabilistic analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115189$53D11114-F702-4DAC-9349-EBFA0B2633D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a4c23ee9323cc5007fffca3f350f0c99c491297","datavalue":{"value":"Davis-Putnam","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115189$47A7AB2E-97FC-4AD1-B2F7-B19809B4F8F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115189$1FB5141B-BBD5-46F5-B4E2-F25AC7078332","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115189$F526AA04-E0C9-4AA7-9E00-C6FE76D7F169","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":"Q1115189$56243C37-75C9-47D0-AB9F-732ACEACB26B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a83312a3e346c7419e7c503e1050470bf3c54e96","datavalue":{"value":{"entity-type":"item","numeric-id":3758242,"id":"Q3758242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115189$13E9ED09-7CC0-4470-8B04-8D8B58AE45B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bc69e791e3ac729c39aee0824be53f2494fd734","datavalue":{"value":{"entity-type":"item","numeric-id":918700,"id":"Q918700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115189$261A37C6-AEA8-4F31-BBE5-DC9B2D79796B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1560f975b41fc89c2a8a5b6289f6e551e273d974","datavalue":{"value":{"entity-type":"item","numeric-id":4771978,"id":"Q4771978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115189$167D8C54-3CA4-4115-9AE7-3FE6FEADB616","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":"Q1115189$4B85D04C-60E5-4FC1-8F71-E4238667B831","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":"Q1115189$3FC86CA1-8ADE-4324-B2BA-2E5B374F28DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ede5963149d40bfce2c69aba6112468c83f3fb90","datavalue":{"value":{"entity-type":"item","numeric-id":1822244,"id":"Q1822244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115189$CD8564AB-D9B8-4E2B-BEBA-F97D3F3C4ACB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a35cc55e5b10a424a85f3ddcd5c540cf5328ff0d","datavalue":{"value":{"entity-type":"item","numeric-id":1249435,"id":"Q1249435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115189$9EA2D35F-CDA0-43EE-975D-A304C5063210","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":"Q1115189$D22C527F-7A20-410B-BCC2-E8274D223DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"865f082c2e39aa822f8117990360da77ecfea3aa","datavalue":{"value":{"entity-type":"item","numeric-id":3694704,"id":"Q3694704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115189$8CB657B9-42DE-4C80-9D69-DEB90964692D","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":"154dac976fc379abaefebc54b35a875e1b3d7fa8","datavalue":{"value":{"amount":"+0.9301565","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1115189$19F587B5-275B-49E4-B74E-422FF38C02FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f5b4347d711ac59d6b334b7fc872e5974d956a6","datavalue":{"value":{"entity-type":"item","numeric-id":3758242,"id":"Q3758242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"171dc408aad58832edeb6382dae6a43830111d29","datavalue":{"value":{"amount":"+0.9224928","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1115189$DEF24D4D-65D8-4917-8CF8-BA0171BBE97F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e839a47c09dfa18abb63f2275844b93176461cf7","datavalue":{"value":{"entity-type":"item","numeric-id":4729354,"id":"Q4729354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a55b54df49caa637ae674bddd5f33d1683ff46d3","datavalue":{"value":{"amount":"+0.9144207","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1115189$DB713ABF-501E-40D8-BFBA-AFE23FF40DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6004857aa6bc21c498ad33bed2a05d343bffda1e","datavalue":{"value":{"entity-type":"item","numeric-id":3081621,"id":"Q3081621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94192860ac746c46dd481b29bc5fe904930c557a","datavalue":{"value":{"amount":"+0.9116801","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1115189$8D9464C6-658D-45AF-B53C-87AD6E32CD7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2660c0a34d8de5b35ffa75edf58b60373668ef9","datavalue":{"value":{"entity-type":"item","numeric-id":808705,"id":"Q808705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5672bbcee9765a9c735fc53d3dab60521e759f7d","datavalue":{"value":{"amount":"+0.9099928","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1115189$C070AFF6-34B9-4443-8149-1A6D8DCCB73D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d14b89c67a6a2ddef8b8cf9ecc0797c7f21f2797","datavalue":{"value":{"entity-type":"item","numeric-id":2767440,"id":"Q2767440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8d23db2dc03a017f870d4198ddd24ef80eeb208","datavalue":{"value":{"amount":"+0.9066086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1115189$2EAD3CD5-58B8-4976-9501-8A80E210D595","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06c333ec1c0069dc1aab83eb54b463cbbf2b2d58","datavalue":{"value":{"entity-type":"item","numeric-id":3707785,"id":"Q3707785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc1797277830a66db9715d53e8d26c346f193c4b","datavalue":{"value":{"amount":"+0.8995252","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1115189$013C0BF2-97C8-4050-B66B-5F32B02082C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7bc8c95cb65fffb94f8ebe1a88bc95da2e10d30","datavalue":{"value":{"entity-type":"item","numeric-id":5486323,"id":"Q5486323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca589615e83a3802dcd31b561df4df5e2d60521c","datavalue":{"value":{"amount":"+0.8981718","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1115189$747900F4-C9DE-4416-9EB5-D1DA07ED3A55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2479c6c8e84b6160d4b613c1b10578187b49658","datavalue":{"value":{"entity-type":"item","numeric-id":4411392,"id":"Q4411392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca589615e83a3802dcd31b561df4df5e2d60521c","datavalue":{"value":{"amount":"+0.8981718","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1115189$02F7AAFF-9870-4099-9A08-985548644068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a2f0d759626dd671d8e961165b77fa1b98dba8b","datavalue":{"value":{"entity-type":"item","numeric-id":918700,"id":"Q918700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6eba3db9548d42d46b33aa2e2ee93a6620fd32fd","datavalue":{"value":{"amount":"+0.8934486","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1115189$1ABD9C9C-A60D-468B-8342-522BE50FEEC2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Probabilistic performance of a heurisic for the satisfiability problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Probabilistic_performance_of_a_heurisic_for_the_satisfiability_problem"}}}}}