{"entities":{"Q1759859":{"pageid":1770601,"ns":120,"title":"Item:Q1759859","lastrevid":51601895,"modified":"2026-01-19T00:45:43Z","type":"item","id":"Q1759859","labels":{"en":{"language":"en","value":"On the gap between \\(\\mathit{ess}(f)\\) and \\(\\mathit{cnf}_{-}\\mathit{size}(f)\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6109928"}},"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":"Q1759859$B430CDD0-459B-48B7-89E8-133B97EE0681","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"858f61a79994b1a2aef40cae17929418c388ffaf","datavalue":{"value":{"text":"On the gap between \\(\\mathit{ess}(f)\\) and \\(\\mathit{cnf}_{-}\\mathit{size}(f)\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1759859$1F5EFAB6-6BDC-4557-82D5-12279A7BE20B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b88bc56453efe820978bf1551a351482f758792c","datavalue":{"value":"1260.06018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759859$6C038562-502C-492F-BC0C-DC2B885EE37A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1094a4d9cd447ca3e59d4f1558fd9d02536babbf","datavalue":{"value":{"entity-type":"item","numeric-id":513284,"id":"Q513284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759859$0BDFB5F5-F4CF-4555-9292-670155EEF21E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba3d53a8d2d19af5629cb054215067c000ae8618","datavalue":{"value":{"entity-type":"item","numeric-id":521802,"id":"Q521802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759859$753C1E2D-2554-4F05-8F47-86A0C105C545","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":"Q1759859$A2772914-695B-4363-8B29-7F298EF1F91E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2f3aa46d2f66375aad8f9f235cf6aa2da570e73e","datavalue":{"value":{"time":"+2012-11-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1759859$F54E7667-160A-479E-B85E-16F20AC61B12","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3d9d26f5421615439a9f5c32a2843972147776a5","datavalue":{"value":"Let \\(f\\) be a Boolean function of \\(n\\) variables. The gap studied in this paper is the ratio \\(\\mathit{cnf}_{-}\\mathit{size}(f)/\\mathit{ess}(f)\\), where the numerator is the minimum number of clauses in a CNF formula representing \\(f\\), while the denominator is the size of the largest set of false points of \\(f\\), no two of which falsify the same implicate of \\(f\\). The authors prove the existence of a function \\(f\\) for which the gap equals \\(\\Theta(n)\\) and of a function \\(f\\) whose gap is at least \\(2^{\\Theta(n)}\\). The case of Horn functions is studied in more detail.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759859$1745A4FA-B92D-4801-B0E7-ED0F0FE86955","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31b64c380fcc4cff66bf21399b51cdd38a2b701d","datavalue":{"value":{"entity-type":"item","numeric-id":588921,"id":"Q588921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759859$A2DD801A-0C2B-401E-B8E3-7771DB6AE1DA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759859$441F4F56-525B-49DC-8AF6-C81580AE184D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759859$DEF6D027-AB24-473E-8BD1-4343DA07FE38","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d11be5838ece139055a089b7d911133be7faf02","datavalue":{"value":"6109928","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759859$7BC0E3D3-2A76-4EBD-829A-11B25E0C682E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e54b2541b44abdffa80a55f59d74e8518d14a635","datavalue":{"value":"DNF","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759859$E9E85CE4-31E2-475C-94B4-1D0AC7A4CBBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0283841a5984d0ead194830870566a24cfd34f06","datavalue":{"value":"CNF","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759859$716D14FA-B0CE-48FB-91BB-E4820223802B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2b3562fa593b0ea952b4d27d20b6ae10babed44","datavalue":{"value":"Horn function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759859$54801EF3-9C16-432E-88AD-8EAE700EA467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf6e47b257014c8d2d90b33c610d51efc201fa59","datavalue":{"value":"formula size","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759859$EC453248-F523-4FDD-BAD2-50F7B31AFE55","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":"Q1759859$C07E1EDE-76A9-4814-9B9A-3FDEFC928AB3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2f70507823dbec27c7fc791ac550af7083dc2e0e","datavalue":{"value":"https://doi.org/10.1016/j.dam.2012.07.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q1759859$E4201816-4CCE-47C2-993C-C059B861B19E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"206ce62bff15ad8301c8eac03e5daf2359cead59","datavalue":{"value":"W1554694446","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759859$45FD1B4D-18B1-43F4-B728-C1FE8AC44942","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"39db57fba228b44d0f2b82fd720438a13308a45f","datavalue":{"value":"10.1016/J.DAM.2012.07.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759859$5C4F0005-88CB-4461-9D20-DB17766C0425","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1d8ffffedff4ecf4d120d8108301fafbbaf37f8","datavalue":{"value":{"entity-type":"item","numeric-id":412324,"id":"Q412324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f016e997abffbc7fc3323b59ff8080d42c134ac","datavalue":{"value":{"amount":"+0.7880880832672119","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":"Q1759859$87B6D448-5C8D-4AA8-A6E5-67D666195A58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fde4737efc9cdef5cb41c47059e8fb00ec4ff090","datavalue":{"value":{"entity-type":"item","numeric-id":4583878,"id":"Q4583878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce8dc7c47bff71441d6d84057483f4dc2d61139c","datavalue":{"value":{"amount":"+0.7827157378196716","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":"Q1759859$5C881426-CA61-4E62-8C7A-60A5C1454917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"873818c68707bbc1be5263c89eb0a585b4085212","datavalue":{"value":{"entity-type":"item","numeric-id":3620386,"id":"Q3620386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cffac7bc26afc9f591ab35ef84cea2447218effc","datavalue":{"value":{"amount":"+0.77228844165802","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":"Q1759859$184A612F-2086-4691-AF29-8C9C27C64D9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6597ce73b99970a27eb52ffa02064571cce6e0ee","datavalue":{"value":{"entity-type":"item","numeric-id":766268,"id":"Q766268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf960331a9e63aef2e909f5e36f516abfe916fde","datavalue":{"value":{"amount":"+0.7549657821655273","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":"Q1759859$6D7D68A7-3402-422E-A8F6-BB1D8067DB5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2762e982855b3ae8467b47f952dad411e7fb9769","datavalue":{"value":{"entity-type":"item","numeric-id":968115,"id":"Q968115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab122c3053c1c13a01b4e0907bdacaffbd4fed6e","datavalue":{"value":{"amount":"+0.7451279163360596","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":"Q1759859$C24A2DB6-8CF8-4BB9-95B4-E3CEEDAAF0A4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1759859","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1759859"}}}}}