Random 2-SAT: Results and problems (Q5958804): Difference between revisions
From MaRDI portal
Latest revision as of 23:30, 3 June 2024
scientific article; zbMATH DE number 1715849
Language | Label | Description | Also known as |
---|---|---|---|
English | Random 2-SAT: Results and problems |
scientific article; zbMATH DE number 1715849 |
Statements
Random 2-SAT: Results and problems (English)
0 references
3 March 2002
0 references
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ás 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.
0 references
satisfiability
0 references
random 2-CNF formulas
0 references
phase transition
0 references
0 references
0 references