Random 2-SAT: Results and problems (Q5958804): Difference between revisions

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.