{"entities":{"Q5958804":{"pageid":8135606,"ns":120,"title":"Item:Q5958804","lastrevid":41127353,"modified":"2025-04-18T10:00:09Z","type":"item","id":"Q5958804","labels":{"en":{"language":"en","value":"Random 2-SAT: Results and problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1715849"}},"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":"Q5958804$28761295-79E0-4CFD-A104-BB519B2B8356","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f07e59033fb7847a74d8880a728408d8f683323d","datavalue":{"value":{"text":"Random 2-SAT: Results and problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5958804$BCE0324D-913A-4D8A-9289-2AB863D05886","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aaeecf208b4a4c555adb68c1159082026979c629","datavalue":{"value":"0983.68080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958804$050E07BF-1F01-411D-AD10-F24CFBD1853C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7112705e6165f7861ca62e26e2924048914f1f0d","datavalue":{"value":"10.1016/S0304-3975(01)00156-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958804$7AC08FBA-3CA2-4021-9F1A-E92C14E1AF5C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a01746797fe0568935cdb8fd9663ac3345e62de","datavalue":{"value":{"entity-type":"item","numeric-id":672469,"id":"Q672469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$337FB20A-B6CE-439C-9947-D5A07804B9E3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$425D1208-644E-43D4-862D-7FEFB9F757EF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de0bbc1f0efc0eda52d8a37720ec217ae66c93cd","datavalue":{"value":{"time":"+2002-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5958804$B91B508B-6325-4B66-95D5-B30D58F1D379","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d4ae0bf173d15fecfe1112f93433d2ebe777fdee","datavalue":{"value":"In the random 2-SAT problem, we are given a set \\(C\\) of \\(m\\) disjunctions of two literals chosen at random within the \\((\\frac{2n}{2})\\) pairs of distinct literals coming from \\(n\\) logical variables. The basic problem is to find out for which values of the ratio \\(\\rho=m/n\\) the disjunctions in \\(C\\) are almost surely simultaneously satisfiable (or almost surely not simultaneously satisfiable) as \\(n\\) tends to infinity. The purpose of this paper is to review the main steps in the solution of this problem, starting with the location of the asymptotic critical ratio around 8 years ago and ending with the recent almost complete solution due to Bollob\u00e1s et al. Thus, this paper is not a review in the usual sense of the word, i.e., it does not include all the known results about random 2-SAT. We will also make a few comments concerning the behaviour of the number of satisfying assignments of random instances of 2-SAT below the critical ratio, a problem relevant to theoretical physics.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958804$2A561F8B-5383-4BA3-B142-F216F392EA92","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958804$ED51C301-3BD6-4D58-8EBB-31AAC2C6E416","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ce9f9d7685d999b651e22905ea6d622a539e83ae","datavalue":{"value":"1715849","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958804$4A279539-3532-406E-85E1-0E0C82679CB7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958804$F3447054-8E20-4089-ABB7-04CCC15A7AE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e23df763c0a15ab7a516e8415e15ba4189d5f402","datavalue":{"value":"random 2-CNF formulas","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958804$8DDA9208-7CC1-4489-B408-06A085935128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"011292841bfecc5a96af7eefb5f2207525532434","datavalue":{"value":"phase transition","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958804$668D9CA5-13A9-4501-BCDD-E0098070E924","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":"Q5958804$BB0DF43F-3FE8-45B8-8996-952B03B3EFE8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"213888b37453d8aaa1d0d856afbc3c9660e59705","datavalue":{"value":{"entity-type":"item","numeric-id":3191968,"id":"Q3191968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$A0EAFA6F-065C-4920-95BC-06030AD3CFDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$56791399-22E6-428D-AFB1-16E2A4EA0731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f31dedd3222c00caf1fa932460b5fc7f23b1737","datavalue":{"value":{"entity-type":"item","numeric-id":2533119,"id":"Q2533119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$CBFC40BA-8C79-489C-97B4-2263D17877BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f554c188b24506bdf878f9958abe8edb0dc6443f","datavalue":{"value":{"entity-type":"item","numeric-id":4704797,"id":"Q4704797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$110E31EB-014D-4446-A282-F012136B55CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93d7559cee62365ca25b0247f0bc285727357cf9","datavalue":{"value":{"entity-type":"item","numeric-id":1285568,"id":"Q1285568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$27E41296-50E0-4BEB-B10F-571F4C883792","rank":"normal"},{"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":"Q5958804$A4CAB1FC-367C-419E-97DD-D0D31C51ABA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c16d03080cf104b6d9587e78c576489f573cb47","datavalue":{"value":{"entity-type":"item","numeric-id":4228436,"id":"Q4228436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$61C0D1F6-5581-4B07-94FB-25F19ED1E8CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3150ccd621fbcc6deb9315c7b7f04d84e34b19c","datavalue":{"value":{"entity-type":"item","numeric-id":4360139,"id":"Q4360139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$D4A2530A-AEF4-437E-B055-BC57C1235F4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a87839e9cce21429fa5c0660242873028f18a79f","datavalue":{"value":{"entity-type":"item","numeric-id":4952608,"id":"Q4952608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$9B276DE7-1564-4112-B76F-B654F9D05A55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$4DB78346-D1EC-4FEA-8EB5-35B853038D41","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":"Q5958804$1F16A0E4-52C0-4C88-A0EB-85E5F352FF6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c460f983de9e6a420aef566a3398a70e655aa7d","datavalue":{"value":{"entity-type":"item","numeric-id":4876696,"id":"Q4876696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$2B537936-786A-4C82-A8A4-595C7EBBE72A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751438aa2bdc3c803c27cb64adcb3ea349c89687","datavalue":{"value":{"entity-type":"item","numeric-id":5096838,"id":"Q5096838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$A5A423CB-6F0A-4723-9919-05B9D5E5F1D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6349cabde3210e4527037a8fc8084c2d3073e31c","datavalue":{"value":{"entity-type":"item","numeric-id":5941282,"id":"Q5941282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$9AEDF424-2A99-4985-B994-B3C02CC842D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b1eb74dc35961dcb1e6adfe219fc2b66bf91b11","datavalue":{"value":{"entity-type":"item","numeric-id":5727090,"id":"Q5727090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$B63FE196-C4A3-4F60-8AB5-FF23A229D784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2e299eeb5096090d0094d25b4d425239dbfde3a","datavalue":{"value":{"entity-type":"item","numeric-id":4492386,"id":"Q4492386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$A81AD22E-935E-4A02-92AF-7AE7824983A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c75f8426f723cb31c8b86032063789c6be1c65f9","datavalue":{"value":{"entity-type":"item","numeric-id":4950549,"id":"Q4950549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$DB1CED59-B81B-420A-8FD8-B817F350C093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0aaff56899c9d83c7edc182fdd871ee1eb568ebd","datavalue":{"value":{"entity-type":"item","numeric-id":1607007,"id":"Q1607007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958804$D6CF1C41-3424-40FD-9198-28B3C491987D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"113088b41a6687d17adc862c3ed9ac5434c9f6b5","datavalue":{"value":{"entity-type":"item","numeric-id":5958803,"id":"Q5958803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71ad67a79f4d8810e9dc669ad403f68f6be27ac9","datavalue":{"value":{"amount":"+0.94516975","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":"Q5958804$4D12A84F-4308-4D73-B565-135F592CEBD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"face938ba9c8ce07d5feef9cfe0e9b11f399b8f9","datavalue":{"value":{"entity-type":"item","numeric-id":1961467,"id":"Q1961467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5833ef75978bae90718027d2d36b452cd4b37c4","datavalue":{"value":{"amount":"+0.9437224","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":"Q5958804$62FAFFC5-2EB1-4E71-BFCA-5E572C27D503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2f425365751659c8f6907ab58ac6dbe7c95b0c6","datavalue":{"value":{"entity-type":"item","numeric-id":1607007,"id":"Q1607007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"049217cee9a1b4d56d309aa3cd28993dc838c7c9","datavalue":{"value":{"amount":"+0.94277406","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":"Q5958804$15156462-40C8-48B6-980D-2D0F77C533A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d42dfc997d767fecb674a5485076892f2f2f587f","datavalue":{"value":{"entity-type":"item","numeric-id":6074640,"id":"Q6074640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a54af576f42cec5cc7cbb081695efe4f90680d8a","datavalue":{"value":{"amount":"+0.9226855","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":"Q5958804$8626AFCC-26CA-435C-8AD1-585FE580AB43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fb671244f8cfbc45680a12e8cd5658e0c30252a","datavalue":{"value":{"entity-type":"item","numeric-id":3192084,"id":"Q3192084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5440e8263d08c83391822b7f0607888e892baa98","datavalue":{"value":{"amount":"+0.91860265","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":"Q5958804$92C24759-3025-40BE-96A2-26A161E32517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1238fbc0c623205593d5898030975d044432588b","datavalue":{"value":{"entity-type":"item","numeric-id":5458513,"id":"Q5458513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fe1392fe863fcad4a7e3b91767fb18b685813c9","datavalue":{"value":{"amount":"+0.9132409","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":"Q5958804$877F0E30-5B55-4991-B9E1-FB61617F1668","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7809fe0b2b70f38046a6b614a4061a73666d8258","datavalue":{"value":{"entity-type":"item","numeric-id":4828949,"id":"Q4828949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aedcd147b860dd84b82b7ff5e9ed4eada97ab65b","datavalue":{"value":{"amount":"+0.9116297","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":"Q5958804$8F0AEC1E-FC5A-4C00-8F71-933E62BFF6D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6d0619605921d6eb4e66cf98ce7822db16b4983","datavalue":{"value":{"entity-type":"item","numeric-id":2642316,"id":"Q2642316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"050db275a095633ed80fedbf71b047a71f6cf97d","datavalue":{"value":{"amount":"+0.9107975","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":"Q5958804$44EEE0DE-7150-4D2F-8B03-499296C2E81F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"985234452789b4a53507f76a69c78e78d0267aeb","datavalue":{"value":{"entity-type":"item","numeric-id":5091218,"id":"Q5091218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53db43c5be3d091404fa54dacb2e12070ccd6f11","datavalue":{"value":{"amount":"+0.9018467","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":"Q5958804$3503E09F-7BE6-49F6-9622-13E0B5ABAB11","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5958804","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5958804"}}}}}