{"entities":{"Q2387184":{"pageid":2397927,"ns":120,"title":"Item:Q2387184","lastrevid":48542410,"modified":"2026-01-05T04:08:02Z","type":"item","id":"Q2387184","labels":{"en":{"language":"en","value":"Random \\(k\\)-SAT: A tight threshold for moderately growing \\(k\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2201518"}},"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":"Q2387184$4C134F66-17C6-4FB5-B796-62EB9D53FD44","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"105d1ecebe29c64d8e782cf467cefe7979b6af21","datavalue":{"value":{"text":"Random \\(k\\)-SAT: A tight threshold for moderately growing \\(k\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2387184$DB17FC02-7BA8-4701-B1ED-3C5C6C95CC1A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"09628cf3745b6f85457afbf4a91dae15cafc5a09","datavalue":{"value":"1083.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2387184$6B9D7E4E-E849-45E9-B6B9-0BC9E111D3F7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c84290e2aa59f5e72197dc6c42e23718498784e5","datavalue":{"value":{"entity-type":"item","numeric-id":704840,"id":"Q704840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2387184$25CBF378-3904-4168-9E8E-5DA2C172CC61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2387184$16BEE94B-13AC-4A88-82B4-E7E1A007360C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2387184$82BF6CD4-3D8F-471A-B5EE-B350C4A15411","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2fa5cbbf808f29fb66da4d33bdc49dbbe5762f9","datavalue":{"value":{"time":"+2006-01-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2387184$30F75138-CE55-4167-AB9C-AEE9B472ED7B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8777a833f6522940d940424348f64c5835445d65","datavalue":{"value":"In this paper a random instance \\(I\\) of \\(k\\)-SAT with \\(n\\) variables and \\(m\\) clauses, where \\(k=k(n)\\) satisfies \\(k-\\log_{2}n\\rightarrow \\infty \\) is considered. Let \\(m_{0}=-n\\ln 2/\\ln (1-2^{-k})=(2^{k}+O(1))n\\ln 2\\), so that \\(2^{n}(1-2^{-k})^{m_{0}}=1\\) and let \\(\\epsilon =\\epsilon (n)>0\\) be such that \\(\\epsilon n\\rightarrow \\infty \\). Let \\(I\\) be a random instance of \\(k\\)-SAT with \\(n\\) variables and \\(m\\) clauses. By using the second moment method it is shown that \\(\\lim _{n\\rightarrow \\infty }\\text{\\textbf{Pr}(}I\\) is satisfiable)","type":"string"},"datatype":"string"},"type":"statement","id":"Q2387184$4B6FCDE8-E28D-4D1C-9DA9-D172C4229FBA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2387184$C6D80237-E0DC-4C2F-81B7-A69468E855FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2387184$98A20358-8D64-4AF9-9E52-5C129CDE55AF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cf729b1f4386f427e9b4150bf0fe642cd0dda65f","datavalue":{"value":"2201518","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2387184$14845527-9E4F-4513-9B71-BBF278FA3EEA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9161657d5fba10184ab322fd0fcb2b7c61ba9274","datavalue":{"value":"random \\(k\\)-SAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q2387184$AAFF0838-B0C6-424A-ABAF-FB4ECE93DCE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22627e2ed257b6fc7d5b8fe82e86af7a622183a8","datavalue":{"value":"tight threshold","type":"string"},"datatype":"string"},"type":"statement","id":"Q2387184$83C5F115-DAFA-43F1-A99E-E56F15F7ECB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b25a5a66786be30e1f9e76aa7171a8621315af0","datavalue":{"value":"second moment method","type":"string"},"datatype":"string"},"type":"statement","id":"Q2387184$50E567FC-8816-437E-AA48-A655AE681304","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2387184$2F80917B-E20E-4908-887F-C57337DB7D6C","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":"Q2387184$D64AB6A6-D441-42DE-B3FA-DD735B7800E2","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c7e25185a61b0df85ecabbf1ca43b30ec6785e51","datavalue":{"value":"Q57401508","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2387184$C836CD99-7630-450E-86BF-E0159CE96585","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4cb1584fa003f05a8e2b33ee3a40d8e1f39603ba","datavalue":{"value":"https://doi.org/10.1007/s00493-005-0017-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q2387184$C3FB2E17-506C-4205-A03F-C2568E44D80D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f6c694b3730bdd76f35347fec8d1ed6e2a56cba0","datavalue":{"value":"W2025593265","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2387184$AE325C0B-CA03-42DE-A23C-E401F8090C86","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b3c47a50e47473ef12c198b075f3b93a4f724e5a","datavalue":{"value":"10.1007/S00493-005-0017-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2387184$61B31C51-2750-4D10-942B-BE41C0D1F651","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"e62af99e9211e118c3343524ccb165a4368b771b","datavalue":{"value":"journals/combinatorica/FriezeW05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2387184$A13CEDA6-B6A2-45E5-921A-5D3992A7C13B","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":"d486bc0130e296aa3f153aee40219c30c1ac3ea8","datavalue":{"value":{"amount":"+0.9331856966018676","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":"Q2387184$AFACF061-ADAF-4AA8-BF3F-5D697B7424E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f96bff9296cce86fe8ecc311e17913f471c18ef","datavalue":{"value":{"entity-type":"item","numeric-id":426783,"id":"Q426783"},"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":"Q2387184$7A6B6F0A-346B-4EE8-B1EF-E3E259F4972C","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":"925a78f5219bb71c2849124857d781bd72eae99c","datavalue":{"value":{"amount":"+0.9065089821815492","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":"Q2387184$B54B37B3-4EA0-4160-B60B-078B2C1F49EA","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":"bca1b89e9dc6eb29c560046df321d5388ed0d463","datavalue":{"value":{"amount":"+0.8886041641235352","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":"Q2387184$285D5D25-3EE3-4AAD-9BFF-5F6B1F7B604E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d50a4c926fba5823993474f6f90660234ae0ffc","datavalue":{"value":{"entity-type":"item","numeric-id":3446816,"id":"Q3446816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46677a619a16cd54ec62eb765ef943504fa52668","datavalue":{"value":{"amount":"+0.8789706230163574","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":"Q2387184$099D70D7-0F01-493D-84D1-0FFEEDC71338","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2387184","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2387184"}}}}}