{"entities":{"Q426783":{"pageid":428550,"ns":120,"title":"Item:Q426783","lastrevid":61758744,"modified":"2026-04-11T01:27:57Z","type":"item","id":"Q426783","labels":{"en":{"language":"en","value":"A note on random \\(k\\)-SAT for moderately growing \\(k\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6045648"}},"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":"Q426783$21658A20-B73F-479D-8075-1965EAB9269B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"901defebd9a98f83e5ab20e6a165640a003ff25f","datavalue":{"value":{"text":"A note on random \\(k\\)-SAT for moderately growing \\(k\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q426783$51795137-2DE2-47AB-81C3-9D056378DE88","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"393af77fbd6b0f89fb18189a1ead895971aaf1f5","datavalue":{"value":"1288.68185","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426783$8CA46526-664A-4D9C-913C-329FEABB24E2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3900f1dd72936e9a81983c93c23516017666df8d","datavalue":{"value":{"entity-type":"item","numeric-id":300229,"id":"Q300229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426783$B58E67FD-E2E5-4B0C-9ECF-2F57E43DB91A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"11839ed9a3457cdf8e2bfc8b703682177c92d237","datavalue":{"value":{"entity-type":"item","numeric-id":1928133,"id":"Q1928133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426783$8416FBAB-AA61-4278-9F13-52B710C5EAD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"81b18c01e024fb6470c92ef8b6a0a1adc622198e","datavalue":{"value":{"entity-type":"item","numeric-id":6774175,"id":"Q6774175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426783$0984045D-DF6C-4AEF-8733-171D99D6F354","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":"Q426783$E6E83357-BB98-45C3-90FC-B24CE5C2842C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4bc8e8f32e3771ea3dc331f4cf4795267b160813","datavalue":{"value":{"time":"+2012-06-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q426783$A1724DA6-0177-4EC4-9F3F-709E22A652A2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a88b59cf405e6f63d884391eb74429a945b3f6ba","datavalue":{"value":"http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i1p24","type":"string"},"datatype":"url"},"type":"statement","id":"Q426783$4288E3A5-463F-4FA9-9640-4200B3BFAA69","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d692f2872011592f8505a0794378338fe66e97bb","datavalue":{"value":"Summary: Consider a random instance \\(I\\) of \\(k\\)-SAT with \\(n\\) variables and \\(m\\) clauses. Suppose that \\(\\theta, c>0\\) are any fixed real numbers. Let \\(k=k(n)\\geq \\big(\\frac{1}{2}+\\theta\\big)\\log_{2}n\\). We prove that  \\[ \\lim_{n\\rightarrow\\infty}\\operatorname{Pr}(I\\;\\text{is satifiable})=\\begin{cases} 1\\quad m\\leq\\big(1-\\frac{c}{\\sqrt{n}}\\big)2^{k}n\\ln 2 \\\\0\\quad m\\geq\\big(1+\\frac{c}{\\sqrt{n}}\\big)2^{k}n\\ln 2.\\end{cases}  \\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q426783$64100D65-351C-4048-8411-86BDADEFF236","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0dd26fa594336927a7a04e8147a405d69e5da239","datavalue":{"value":"68Q87","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426783$70A6699C-8251-4E4D-ADEE-6FE18D7C8B47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426783$6BE7D399-4C5C-4236-A289-2E1651894377","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426783$03A9B7D5-DF7B-46F7-9A80-5961015A32C4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0857750555fb58e528b473b597586331bc7bb4ab","datavalue":{"value":"6045648","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426783$09CCB0A2-2BC0-4C69-9D61-FD780F5BC670","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea9bf80053f5b2b93d2d06d6e47daf003fd831e1","datavalue":{"value":"k-SAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q426783$C562E227-345D-4ACC-8DF8-A4B0F45662CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"011292841bfecc5a96af7eefb5f2207525532434","datavalue":{"value":"phase transition","type":"string"},"datatype":"string"},"type":"statement","id":"Q426783$57B570DD-24F4-48D4-9DD1-6865F32372A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b25a5a66786be30e1f9e76aa7171a8621315af0","datavalue":{"value":"second moment method","type":"string"},"datatype":"string"},"type":"statement","id":"Q426783$D8CC0AEA-97CF-4040-94B3-542D7087A289","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":"Q426783$AE1E04EE-4011-4201-84A9-5D4B80F424E8","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"b7c8e59241e446e7f89cf3a9ef7d6dfc8838e7ec","datavalue":{"value":"bafkreie6t3u3mu5kuqacwoq2hwcqdcuhtgypmkqueodf545jinjgbqbuva","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426783$17E63EB2-3CCC-482B-AEA2-5216E2577B40","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0185050f71bda7ac075da4d5af7ac4b7a6e99ae7","datavalue":{"value":{"entity-type":"item","numeric-id":1010652,"id":"Q1010652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1fbdc81a1886781c7f95f8efa61b87b59af90e5","datavalue":{"value":{"amount":"+0.941832721233368","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":"Q426783$56525551-26B2-4EF7-83B1-7C6AD8DBDA5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a141f389c4df414090ed7db15d2d5886a29a6641","datavalue":{"value":{"entity-type":"item","numeric-id":2387184,"id":"Q2387184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df3db6af6835870ef7c2e108b1072bd320d0b9da","datavalue":{"value":{"amount":"+0.9289888739585876","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":"Q426783$9BAFB92C-4F33-45C9-A6CE-D21DF05B2A45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aefa707b5b413fbce23c4b586e4bc1aed08fa5c6","datavalue":{"value":{"entity-type":"item","numeric-id":4821034,"id":"Q4821034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ace261b12017fb791fa115dc93be8c4bf74d4cf6","datavalue":{"value":{"amount":"+0.8552535176277161","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":"Q426783$F93F5E33-0B57-4647-94EF-B542C55AC0B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24b0081dc2f15dc73a7215324226f87bce3b6029","datavalue":{"value":{"entity-type":"item","numeric-id":3581271,"id":"Q3581271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a2f63aceaab5b47f88800d69a82fd89c994164e","datavalue":{"value":{"amount":"+0.8449975252151489","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":"Q426783$B4DDEA87-5BEB-415D-99E2-0E9751AB320D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ceaddce235366296c48c86158fd23909d4ae9d41","datavalue":{"value":{"entity-type":"item","numeric-id":2171413,"id":"Q2171413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"417f78137dec91f80deea83ec6d18f2c7e455286","datavalue":{"value":{"amount":"+0.8111081719398499","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":"Q426783$EB1B6F3F-F8E9-44CF-936C-B57E9BFECD0D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on random \\(k\\)-SAT for moderately growing \\(k\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_random_%5C(k%5C)-SAT_for_moderately_growing_%5C(k%5C)"}}}}}