{"entities":{"Q1010894":{"pageid":1012742,"ns":120,"title":"Item:Q1010894","lastrevid":66595692,"modified":"2026-04-12T11:11:15Z","type":"item","id":"Q1010894","labels":{"en":{"language":"en","value":"On the size of minimal unsatisfiable formulas"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5541059"}},"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":"Q1010894$08DB8AA2-702D-43E8-99B7-9C5DA449D4D4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c764349b528dab6e8d47fa584c066ab2859aaafa","datavalue":{"value":{"text":"On the size of minimal unsatisfiable formulas","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010894$E7106DCF-2B02-4064-8AAF-A5CC71E1AAFA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"edfe3213c993a47e552215cd24c44d2e40463a6b","datavalue":{"value":"1178.68290","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010894$C5774801-0513-4D80-96C3-532394999E8F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6c7051c205c12629057479729f5c7f60a52cca20","datavalue":{"value":{"entity-type":"item","numeric-id":345087,"id":"Q345087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010894$4DB71B36-8E3A-454B-AD62-F18DA58734D1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010894$A48D5266-283A-4939-A842-B8B9A25364EC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010894$17AE3AD5-5589-4DF0-A349-BA72933307DE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d92609db2bd399f90305c432dd62a8c44928ebbe","datavalue":{"value":"https://arxiv.org/abs/0811.0427","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010894$0E4BAEA5-6956-4998-BABF-D38180491C9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"da6774699a50c2060525fa448f488e3b35da8fbd","datavalue":{"value":"https://eudml.org/doc/117286","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010894$D047655D-3195-4353-B1A4-CEA65A123DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"71b56299dc62e9138a0e709e986925c41e652e8b","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1n3.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010894$6132DEFD-96FA-4804-9522-C1695F47E787","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"01fff18dcc3ccd8c4023fd32b3c1cc3ddec8089d","datavalue":{"value":"Summary: An unsatisfiable formula is called minimal if it becomes satisfiable whenever any of its clauses are removed. We construct minimal unsatisfiable \\(k\\)-SAT formulas with \\(\\Omega(n^k)\\) clauses for \\(k \\geq 3\\), thereby negatively answering a question of Rosenfeld. This should be compared to the result of \\textit{L. Lov\u00e1sz} [Stud. Sci. Math. Hung. 11, 113--114 (1976; Zbl 0425.05026)] which asserts that a critically 3-chromatic \\(k\\)-uniform hypergraph can have at most \\(\\binom {n}{k-1}\\) edges.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010894$B4F3F6A1-DC34-4FDF-9D23-C499589B49EC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010894$29564A3A-6794-4DF9-9123-936D29CD55CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010894$2AA931C9-A72C-487D-B38A-9CE188B70543","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010894$478B081A-B0A0-4811-8BEF-1F6533A4E582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010894$DCBA7554-8BD6-49EE-A334-4AF4EC208307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010894$F20A112A-BACF-47C3-8823-C6E727463D06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010894$499FF30E-5876-4776-9FF3-E9D0EE05CC98","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ff0fd97e6c8f0624120f02098776d495ee7f5fbb","datavalue":{"value":"5541059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010894$CED34982-78AE-457F-BC7D-4991B2C82FEC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7390a4ff52dd86c09e8b932f6a2cb9f6017e2b1","datavalue":{"value":"minimal unsatisfiable formulas","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010894$F5E094A8-94CB-45DE-9974-7EB41A93C620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d5bcec278fcb6c130addc2e5de940ee957bd3b4","datavalue":{"value":"critically 3-connected hypergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010894$6344BDEA-A159-42E1-A4FB-4D16C99C19E9","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":"Q1010894$F8526A52-A375-45CC-89A4-81979DAD0E8F","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"d9d32be7f27b919921b3718d442450e9ede2c73b","datavalue":{"value":"bafkreig3etahtgxwrjs7vtqdkm5yheah5ic54dseq5kqsupfy4qza6k5qm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010894$F94E592F-499A-41CA-BDDD-6BD7F7A8E1F2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f8e35f8e3bb7b596a6ae2dd0e6c20e4c92f9e21","datavalue":{"value":{"entity-type":"item","numeric-id":1087560,"id":"Q1087560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"947af901fe33abdf17a6d5124b6118d1f24a15ec","datavalue":{"value":{"amount":"+0.8493617177009583","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":"Q1010894$A95F9E2A-657D-452D-B5EA-367523BF5661","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"875e8f2bfecf0bcbd77fc501b60ebbd080fc3230","datavalue":{"value":{"entity-type":"item","numeric-id":2743691,"id":"Q2743691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b38ba36f66ee0f178002163aec31910a867ee8f8","datavalue":{"value":{"amount":"+0.8226647973060608","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":"Q1010894$60EDC78C-643E-4107-862A-2574E2C4E3E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ae02f1045f7565e768e0af18e78dc11abf32c96","datavalue":{"value":{"entity-type":"item","numeric-id":1277336,"id":"Q1277336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c5517de6de89e58127df12efcc54ceea740f87f","datavalue":{"value":{"amount":"+0.8170939087867737","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":"Q1010894$3A87704B-BE17-47DD-8C11-0105FB1E689E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e46b9d50bd05642ead4f78dd5455c8bbbb978580","datavalue":{"value":{"entity-type":"item","numeric-id":1961649,"id":"Q1961649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eadb22063953287390f77826deba6a3f2d8e3fe0","datavalue":{"value":{"amount":"+0.8091736435890198","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":"Q1010894$66A0354C-A948-462E-854C-B6F445AA4532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b496d73cc71f03723d822ff7533eb9713f4da25","datavalue":{"value":{"entity-type":"item","numeric-id":5473177,"id":"Q5473177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"313e1309306aedd920c2db0e50f2c1be3489f283","datavalue":{"value":{"amount":"+0.8060800433158875","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":"Q1010894$06A2564C-EF6B-48B8-925D-128782D85537","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the size of minimal unsatisfiable formulas","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_size_of_minimal_unsatisfiable_formulas"}}}}}